有N个人，M个星球，有一个N*M的矩阵，表示某个人是否可以去某个星球。问你这些人能不能全安排到这些星球上？
做过了之前的几道题，这道题明显就是网络流了，但是，这道题考了缩点/状态压缩，因为N取值上限太大了，每个人都建一个点会超内存的，考虑M的上限很小（10），对所有人而言，去星球的状态最多2^M = 1<<M种，所以每种状态建一个点就好了（每种状态代表一类人，这类人完全等价）。
输入给的是01序列，所以正好由这一行二进制得出十进制的状态编号，这个相当于压缩的过程。注意在对状态编号解压时要按照相同的位处理顺序（解压就是判断状态编号的二进制表示中某一位是不是1，用if( state & (1<<x) )来判断二进制某位是不是1）。
#include#include #include #include #include #include #include using namespace std;const int MAX = 2 + (1 << 10) + 10 + 10; //const int INF = 1e9;int N, M;int flow;int cnt[1 << 10];struct Edge{ int from, to, flow, cap;};vector ve;vector v[MAX];int level[MAX];int cur[MAX];void addEdge(int from, int to, int weight){ ve.push_back(Edge{ from,to,0,weight }); ve.push_back(Edge{ to,from,0,0 }); v[from].push_back(ve.size() - 2); v[to].push_back(ve.size() - 1);}void init(){ ve.clear(); for (int i = 0; i < 2 + (1 << M) + M; i++) // debug 思路转换后没及时改正的地方 v[i].clear(); flow = 0; memset(cnt, 0, sizeof cnt);}bool bfs(int dst){ queue q; memset(level, -1, sizeof level); q.push(0); level[0] = 0; for (; !q.empty();) { int x = q.front(); q.pop(); for (int i = 0; i < v[x].size(); i++) { Edge& e = ve[v[x][i]]; if (level[e.to] < 0 && e.flow < e.cap) { level[e.to] = level[x] + 1; q.push(e.to); } } } return level[dst] >= 0;}int dfs(int x, int dst, int f){ if (x == dst || f == 0) return f; for (int& i = cur[x]; i < v[x].size(); i++) { Edge& e = ve[v[x][i]]; int f0; if (level[e.to] == level[x] + 1 && (f0 = dfs(e.to, dst, min(f, e.cap - e.flow)))) { e.flow += f0; ve[v[x][i] ^ 1].flow -= f0; return f0; } } return 0;}int main(){ int d; for (; ~scanf("%d%d", &N, &M);) { init(); for (int i = 0; i < N; i++) { int state = 0; for (int j = 0; j < M; j++) { scanf("%d", &d); if (d) state += (1 << j); } cnt[state]++; } for (int i = 0; i < (1 << M); i++) { addEdge(0, i + 1, cnt[i]); for (int j = 0; j < M; j++) { if (i&(1 << j)) addEdge(i + 1, (1 << M) + j + 1, INF); } } for (int i = 1; i <= M; i++) { scanf("%d", &d); addEdge((1 << M) + i, (1 << M) + M + 1, d); } for (; bfs((1 << M) + M + 1);) { memset(cur, 0, sizeof cur); int temp; for (; temp = dfs(0, (1 << M) + M + 1, INF);) flow += temp; } printf("%s\n", flow == N ? "YES" : "NO"); } return 0;}