题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3605
题目大意:
地球有n个人(1 <= n <= 100000),有m个星球(1 <= m <= 10)每个人都有一些想去的星球,用一行成都为m的01串表示。1:表示想去这个星球,0表示不想去。每个星期有居住的人口数限制,问你能不能安排好所有人。
#include<bits/stdc++.h> #define INF 1e9 using namespace std; const int maxn =2000+10; struct Edge { int from,to,cap,flow; Edge(){} Edge(int f,int t,int c,int fl):from(f),to(t),cap(c),flow(fl){} }; struct Dinic { int n,m,s,t; vector<Edge> edges; vector<int> G[maxn]; int cur[maxn]; int d[maxn]; bool vis[maxn]; void init(int n,int s,int t) { this->n=n, this->s=s, this->t=t; edges.clear(); for(int i=0;i<n;i++) G[i].clear(); } void AddEdge(int from,int to,int cap) { edges.push_back( Edge(from,to,cap,0) ); edges.push_back( Edge(to,from,0,0) ); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { queue<int> Q; Q.push(s); memset(vis,0,sizeof(vis)); d[s]=0; vis[s]=true; while(!Q.empty()) { int x=Q.front(); Q.pop(); for(int i=0;i<G[x].size();++i) { Edge& e=edges[G[x][i]]; if(!vis[e.to] && e.cap>e.flow) { d[e.to]=1+d[x]; vis[e.to]=true; Q.push(e.to); } } } return vis[t]; } int DFS(int x,int a) { if(x==t || a==0) return a; int flow=0,f; for(int& i=cur[x];i<G[x].size();++i) { Edge& e=edges[G[x][i]]; if(d[e.to]==d[x]+1 && (f=DFS(e.to,min(a,e.cap-e.flow) ) )>0) { e.flow +=f; edges[G[x][i]^1].flow -=f; flow +=f; a-=f; if(a==0) break; } } return flow; } int max_flow() { int ans=0; while(BFS()) { memset(cur,0,sizeof(cur)); ans += DFS(s,INF); } return ans; } }DC; int A[1024]; int main(){ int n, m, x; while(~scanf("%d%d", &n, &m)){ memset(A, 0, sizeof(A)); int start, tend; start=0, tend=1024+m+1; DC.init(tend+5, start, tend); for(int i=1; i<=n; i++){ int pos=0; for(int j=1; j<=m; j++){ scanf("%d", &x); pos=pos*2+x; } A[pos]++; } for(int s=0; s<(1<<10); s++){ if(A[s]){ DC.AddEdge(start, s, A[s]); for(int k=0; k<m; k++){ if(s&(1<<k)){ DC.AddEdge(s, 1024+k+1, A[s]); } } } } for(int i=1; i<=m; i++){ scanf("%d", &x); DC.AddEdge(1024+i, tend, x); } if(DC.max_flow()==n){ printf("YES\n"); } else{ printf("NO\n"); } } return 0; }