网络流
农夫为他的 N (1 ≤ N ≤ 100) 牛准备了 F (1 ≤ F ≤ 100)种食物和 D (1 ≤ D ≤ 100) 种饮料。每头牛都有各自喜欢的食物和饮料，而每种食物或饮料只能分配给一头牛。最多能有多少头牛可以同时得到喜欢的食物和饮料？
Input
第一行输入三个整数N, F, D
接下来n行，每行先输入两个整数 Fi 和 Di，分别表示编号为 i 的牛喜欢的食物和饮料的数量，接下来的Fi个整数表示第i头牛喜欢的食物的编号，最后Di个整数表示第i头牛喜欢的饮料的编号。
Output 输出同时得到喜欢的食物和饮料的牛的数量的最大值。
Sample Input4 3 3 2 2 1 2 3 1 2 2 2 3 1 2 2 2 1 3 1 2 2 1 1 3 3Sample Output
3
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 const int amn=1e6+5; 7 const int inf=1e9; 8 int dis[amn],head[amn],n,f,d,tot; 9 struct node{ 10 int to,next,flow,c; 11 }edge[amn<<1]; 12 void init(){ 13 memset(head,-1,sizeof(head)); 14 tot=0; 15 } 16 void add(int u,int v,int c){ 17 edge[tot].to=v; 18 edge[tot].flow=c; 19 edge[tot].next=head[u]; 20 head[u]=tot++; 21 edge[tot].to=u; 22 edge[tot].flow=0; 23 edge[tot].next=head[v]; 24 head[v]=tot++; 25 } 26 int bfs(int s,int t){ 27 queue<int> q; 28 memset(dis,-1,sizeof(dis)); 29 dis[s]=0; 30 q.push(s); 31 while(!q.empty()){ 32 int x=q.front(); 33 q.pop(); 34 if(x==t)return 1; 35 for(int i=head[x];i!=-1;i=edge[i].next){ 36 int v=edge[i].to; 37 if(edge[i].flow&&dis[v]==-1){ 38 dis[v]=dis[x]+1; 39 q.push(v); 40 } 41 } 42 } 43 if(dis[t]==-1)return 0; 44 return 1; 45 } 46 int dfs(int s,int flow){ 47 if(s==2*n+d+f+1)return flow; 48 int ans=0; 49 for(int i=head[s];i!=-1;i=edge[i].next){ 50 int v=edge[i].to; 51 if(edge[i].flow&&dis[v]==dis[s]+1){ 52 int f=dfs(v,min(flow-ans,edge[i].flow)); 53 edge[i].flow-=f; 54 edge[i^1].flow+=f; 55 ans+=f; 56 if(ans==flow)return ans; 57 } 58 } 59 return ans; 60 } 61 int Dinc(int s,int t){ 62 int flow=0; 63 while(bfs(s,t)){ 64 flow+=dfs(s,inf); 65 } 66 return flow; 67 } 68 int main(){ 69 while(~scanf("%d%d%d",&n,&f,&d)){ 70 init(); 71 int s=0,t=2*n+f+d+1; 72 for(int i=1;i<=f;i++){ 73 add(s,2*n+i,1); 74 } 75 for(int i=1;i<=d;i++){ 76 add(2*n+f+i,2*n+f+d+1,1); 77 } 78 for(int i=1;i<=n;i++){ 79 add(i,i+n,1); 80 } 81 int in,di,fi; 82 for(int i=1;i<=n;i++){ 83 scanf("%d%d",&fi,&di); 84 for(int j=1;j<=fi;j++){ 85 scanf("%d",&in); 86 add(2*n+in,i,1); 87 } 88 for(int j=1;j<=di;j++){ 89 scanf("%d",&in); 90 add(n+i,2*n+f+in,1); 91 } 92 } 93 printf("%d\n",Dinc(s,t)); 94 } 95 }
