本文共 3352 字，大约阅读时间需要 11 分钟。
#include #include #include #include #include #include #include #include #include #include using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; const int big=50000; int max(int a,int b) {return a>b?a:b;}; int min(int a,int b) {return a G[500]; void add_edge(int f,int t) { G[f].push_back((Edge){t,1,G[t].size()}); G[t].push_back((Edge){f,0,G[f].size()-1}); } void bfs(int s) { queue q; q.push(s); level[s]=1; //cout< <<" "< < 0) { Edge e=G[now][i]; //printf("%d: %d\n",now,e.to); if(level[e.to]<0) { level[e.to]=level[now]+1; //printf("%d %d: %d %d\n",now,level[now],e.to,level[e.to]); q.push(e.to); } } } } int dfs(int s,int t) { if(s==t) return 1; for(int i=0;i level[s]&&e.cap>0&&dfs(e.to,t)) { e.cap-=1; G[e.to][e.rev].cap+=1; return 1; } } return 0; } int max_flow(int s,int t) { int ans=0; for(;;) { memset(level,-1,sizeof(level)); bfs(s); //printf("%d\n",level[t]); if(level[t]<0) return ans; while(dfs(s,t)) ans++; } } void init() { for(int i=0;i<=500;i++) G[i].clear(); } int main() { int n,f,d,fx,dx,temp; while(~scanf("%d %d %d",&n,&f,&d)) { init(); for(int i=1;i<=n;i++) { scanf("%d %d",&fx,&dx); for(int j=1;j<=fx;j++) { scanf("%d",&temp); add_edge(temp,f+i); } for(int j=1;j<=dx;j++) { scanf("%d",&temp); add_edge(i+n+f,2*n+f+temp); } } for(int i=1;i<=f;i++) add_edge(0,i); for(int i=1;i<=d;i++) add_edge(f+2*n+i,f+d+2*n+1); for(int i=1;i<=n;i++) add_edge(i+f,i+n+f); /* for(int i=0;i<=f+d+2*n+1;i++) for(int j=0;j 0) printf("%d: %d %d\n",i,G[i][j].to,G[i][j].cap); */ printf("%d\n",max_flow(0,f+d+2*n+1)); } return 0; }
#include #include #include #include #include #include #include #include #include #include using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; const int big=50000; int max(int a,int b) { return a>b?a:b;}; int min(int a,int b) { return a G[500]; void add_edge(int f,int t) { G[f].push_back((Edge){ t,1,G[t].size()}); G[t].push_back((Edge){ f,0,G[f].size()-1}); } void bfs(int s) { queue q; q.push(s); level[s]=1; while(q.size()) { int now=q.front();q.pop(); for(int i=0;i 0) { level[e.to]=level[s]+1; q.push(e.to); } } } } int dfs(int s,int t) { if(s==t) return 1; for(int i=0;i level[s]&&dfs(e.to,t)) { G[s][i].cap-=1; G[e.to][G[s][i].rev].cap+=1; return 1; } } return 0; } void max_flow(int s,int t) { memset(level,-1,sizeof(level)); int ans=0; for(;;) { bfs(s); if(level[t]<0) break; while(dfs(s,t)) ans++; } printf("%d\n",ans); } int main() { int n,f,d,fx,dx,temp; while(~scanf("%d %d %d",&n,&f,&d)) { for(int i=1;i<=n;i++) { scanf("%d %d",&fx,&dx); for(int j=1;j<=fx;j++) { scanf("%d",temp); add_edge(temp,f+i); } for(int j=1;j<=dx;j++) { scanf("%d",&temp); add_edge(i+n+f,2*n+f+temp); } } for(int i=1;i<=f;i++) add_edge(0,i); for(int i=1;i<=d;i++) add_edge(f+2*n+i,f+d+2*n+1); max_flow(0,f+d+2*n+1); } return 0; }
转载地址：http://ztgsi.baihongyu.com/