POJ 3281 Dining(最大流+拆点)

题目大意：
农夫为他的 N (1 ≤ N ≤ 100) 牛准备了 F (1 ≤ F ≤ 100)种食物和 D (1 ≤ D ≤ 100) 种饮料。每头牛都有各自喜欢的食物和饮料，
而每种食物或饮料只能分配给一头牛。最多能有多少头牛可以同时得到喜欢的食物和饮料？

解题思路：
令st=0为源点，en=f+2*n+1为汇点，
st向每种食物建流量为1的边，
每种食物向喜欢它的牛（拆点1）建流量为1的边，
眉头牛的拆点之间建流量为1的边，
每头牛（拆点2）向它喜欢的饮料建流量为1的边，
每种饮料向en建流量为一的边。
注意，一定要将牛拆点，如果一头牛只用一个点然后连接饮料和食物，会导致一头牛同时消耗多种食物和饮料。
这个自己画图模拟一下就能理解了。

代码

  1 /*
  2 此题需要对奶牛进行拆点，左边食物（水），中间奶牛1，奶牛2，右边水（食物） 
  3 拆点是为了限制奶牛只能吃一份食物和谁，若不对奶牛进行拆点，则一头奶牛可能会吃多份食物和水 
  4 */
  5 #include<iostream>
  6 #include<cstdio>
  7 #include<cstring>
  8 #include<cmath>
  9 #include<algorithm>
 10 #include<queue>
 11 #include<vector>
 12 #define LL long long
 13 #define pii pair<int,int>
 14 #define pll pair<long long,long long>
 15 #define rep(i,a,b) for(int i=a;i<=b;i++)
 16 #define per(i,a,b) for(int i=a;i>=b;i--)
 17 #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
 18 #define bug cout<<"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"<<endl;
 19 #define bugc(_) cout << (#_) << " = " << (_) << endl;
 20 using namespace std;
 21 const int N=1e6+5;
 22 const int M=1e6+5;
 23 const int INF=0x3f3f3f3f;
 24 
 25 struct node{
 26     int to,next,flow;
 27 }edge[M*2];
 28 
 29 int cnt,st,en;
 30 int head[N],dep[N];
 31 
 32 void init(){
 33     cnt=2;
 34     memset(head,0,sizeof(head));
 35 }
 36 
 37 void link(int u,int v,int flow){
 38     edge[cnt]=node{v,head[u],flow};
 39     head[u]=cnt++;
 40     edge[cnt]=node{u,head[v],0};
 41     head[v]=cnt++;
 42 }
 43 
 44 int bfs(){
 45     memset(dep,0,sizeof(dep));
 46     dep[st]=1;
 47     queue<int>q;
 48     q.push(st);
 49     while(!q.empty()){
 50         int u=q.front();
 51         q.pop();
 52         for(int i=head[u];i;i=edge[i].next){
 53             node t=edge[i];
 54             if(t.flow&&!dep[t.to]){
 55                 dep[t.to]=dep[u]+1;
 56                 q.push(t.to);
 57             }
 58         }
 59     }
 60     return dep[en];
 61 }
 62 
 63 int dfs(int u,int fl){
 64     if(u==en) return fl;
 65     int tmp=0;
 66     for(int i=head[u];i&&fl;i=edge[i].next){
 67         node &t=edge[i];
 68         if(t.flow&&dep[t.to]==dep[u]+1){
 69             int x=dfs(t.to,min(t.flow,fl));
 70             if(x>0){
 71                 t.flow-=x;
 72                 edge[i^1].flow+=x;
 73                 tmp+=x;
 74                 fl-=x;
 75             }
 76         }
 77     }
 78     if(!tmp) dep[u]=-2;
 79     return tmp;
 80 }
 81 
 82 int dinic(){
 83     int ans=0;
 84     while(bfs()){
 85         while(int d=dfs(st,INF)){
 86             ans+=d;
 87         }
 88     }
 89     return ans;
 90 }
 91 
 92 int main(){
 93     int n,f,d;
 94     while(~scanf("%d%d%d",&n,&f,&d)){
 95         init();
 96         st=0,en=f+2*n+d+1;
 97         for(int i=1;i<=n;i++){
 98             int t1,t2;
 99             scanf("%d%d",&t1,&t2);
100             for(int j=1;j<=t1;j++){
101                 int x;
102                 scanf("%d",&x);
103                 link(x,i+f,1);
104             }
105             for(int j=1;j<=t2;j++){
106                 int x;
107                 scanf("%d",&x);
108                 link(i+f+n,x+f+2*n,1);
109             }
110         }
111         for(int i=1;i<=f;i++) link(st,i,1);
112         for(int i=1;i<=n;i++) link(i+f,i+f+n,1);
113         for(int i=1;i<=d;i++) link(i+f+2*n,en,1);
114         printf("%d
",dinic());
115     }
116     return 0;
117 }