题意：n(n<=10^5)个人，m(m<=10)个星球，给你一个矩阵，告诉你第i个人是否可以逃到第j个星球上（输入略坑。。貌似是倒着来的），然后告诉你每个星球上最多可以容纳多少人，要你判断这n个人是否能够全部被转移到这m个星球上。
建图还是很好想的，但是如果以每个人都作为一个点建图的话，点就太多了，肯定要TLE。由于m比较小，所以可以考虑状态压缩。每种状态i，每个二进制位的1表示此类人可以居住在一个星球上，这样一来，最多2^10=1024种状态。统计出来每种状态有多少人，然后就可以建边了。对于每种状态，对应边(S,i,count(i)),如果状态i下的人可以去j星球，对应边(i,j,count(i))，对于每个星球j的容纳人数上限，对应边(j,T,limit)，跑最大流判是否满流。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define INF 1<<30 6 #define maxn 1100 7 #define maxm 30000 8 using namespace std; 9 10 int v[maxm],next[maxm],w[maxm]; 11 int first[maxn],d[maxn],work[maxn],q[maxn]; 12 int e,S,T; 13 int bit[maxn],count_bit[maxn]; 14 void init(){ 15 e = 0; 16 memset(first,-1,sizeof(first)); 17 } 18 19 void add_edge(int a,int b,int c){ 20 //printf("add:%d to %d,cap = %d ",a,b,c); 21 v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++; 22 v[e] = a;next[e] = first[b];w[e] = 0;first[b] = e++; 23 } 24 25 int bfs(){ 26 int rear = 0; 27 memset(d,-1,sizeof(d)); 28 d[S] = 0;q[rear++] = S; 29 for(int i = 0;i < rear;i++){ 30 for(int j = first[q[i]];j != -1;j = next[j]) 31 if(w[j] && d[v[j]] == -1){ 32 d[v[j]] = d[q[i]] + 1; 33 q[rear++] = v[j]; 34 if(v[j] == T) return 1; 35 } 36 } 37 return 0; 38 } 39 40 int dfs(int cur,int a){ 41 if(cur == T) return a; 42 for(int &i = work[cur];i != -1;i = next[i]){ 43 if(w[i] && d[v[i]] == d[cur] + 1) 44 if(int t = dfs(v[i],min(a,w[i]))){ 45 w[i] -= t;w[i^1] += t; 46 return t; 47 } 48 } 49 return 0; 50 } 51 52 int dinic(){ 53 int ans = 0; 54 while(bfs()){ 55 memcpy(work,first,sizeof(first)); 56 while(int t = dfs(S,INF)) ans += t; 57 } 58 return ans; 59 } 60 61 int bitcount(int x){ 62 int b; 63 for(b = 0;x != 0;x &= (x-1)) b++; 64 return b; 65 } 66 67 int main() 68 { 69 for(int i = 0;i < 1024;i++) 70 bit[i] = bitcount(i); 71 int n,m; 72 while(scanf("%d%d",&n,&m) == 2){ 73 init(); 74 memset(count_bit,0,sizeof(count_bit)); 75 S = (1<<m)+m,T = S+1; 76 for(int i = 0;i < n;i++){ 77 int tmp,sum = 0; 78 for(int j = 0;j < m;j++){ 79 scanf("%d",&tmp); 80 sum |= (tmp<<(m-1-j)); 81 } 82 count_bit[sum]++; 83 } 84 for(int i = 0;i < (1<<m);i++){ //枚举状态 85 if(count_bit[i]){ 86 add_edge(S,i,count_bit[i]); 87 for(int j = 0;j < m;j++){ 88 if(i & (1<<j)) //第i状态下的人可以住在j星上 89 add_edge(i,(1<<m)+j,count_bit[i]); 90 } 91 } 92 } 93 for(int i = 0;i < m;i++){ 94 int num; 95 scanf("%d",&num); 96 add_edge((1<<m)+i,T,num); 97 } 98 int ans = dinic(); 99 //printf("ans = %d ",ans); 100 if(ans == n) printf("YES "); 101 else printf("NO "); 102 } 103 return 0; 104 }