N 個人，每人有 M 種技能（0/1 向量）。M 個星球，每星球有容量上限。每人只能去技能匹配的星球（人技能向量與星球需求向量按位與全為 1？實際為：人技能 1 的位置，星球必須也有 1？題目實為：人有一組技能，星球要求一組技能，人技能包含星球要求即可去）。問是否所有人都能安排到星球。
N 達 10⁵，但技能組合極少。將相同技能的人合併為一個節點（縮點），容量為該技能出現次數。構建流網絡：
最大流 = N 則可行。
mask = Σ skill[i]<。 cnt[mask]。need[planet]。(mask & need[planet]) == need[planet]（人技能包含星球需求）。#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAXV = 2000; // 1024 + 10 + 2
struct Edge { int to, cap, rev; };
vector<Edge> G[MAXV];
int level[MAXV], iter[MAXV];
void add_edge(int from, int to, int cap) {
G[from].push_back({to, cap, (int)G[to].size()});
G[to].push_back({from, 0, (int)G[from].size()-1});
}
void bfs(int s) {
fill(level, level+MAXV, -1);
queue<int> q; level[s]=0; q.push(s);
while(!q.empty()) {
int v=q.front(); q.pop();
for(auto &e:G[v]) if(e.cap>0 && level[e.to]<0) {
level[e.to]=level[v]+1; q.push(e.to);
}
}
}
int dfs(int v, int t, int f) {
if(v==t) return f;
for(int &i=iter[v]; i0 && level[v]0) { e.cap-=d; G[e.to][e.rev].cap+=d; return d; }
}
}
return 0;
}
int max_flow(int s, int t) {
int flow=0, f;
while(true) {
bfs(s);
if(level[t]<0) return flow;
fill(iter, iter+MAXV, 0);
while((f=dfs(s,t,INF))>0) flow+=f;
}
}
int main() {
int n, m;
while(scanf("%d%d", &n, &m)==2) {
for(int i=0;i cnt(1< cap(m);
for(int j=0;j skill nodes
for(int mask=0; mask<(1< planet
for(int mask=0; mask<(1< T
for(int p=0; p
關鍵優化：縮點
- 原圖：N(10⁵) 人節點 + M 星球 ⇒ 邊數巨大，Dinic/ISAP 超時/超內存。
- 縮點後：≤1024 技能節點 + 10 星球 ⇒ 節點 ~1034，邊 ~10240，極小。
- ISAP/Dinic 瞬時跑完。
複雜度分析
- 構圖：O(N·M + 2ᴹ·M) ≈ 10⁶ + 10⁴。
- 最大流：O(V²E) ISAP，V≈10³, E≈10⁴ ⇒ 極快。
- 空間：O(V+E) ≈ 10⁴。
總結
本題核心是「狀態壓縮 + 縮點 + 最大流」。大數據範圍下，發現狀態空間小（2ᴹ）是破題關鍵。將同狀態實體合併為帶容量節點，將分配問題建模為流網絡，是經典套路。
