POJ 3281 简单构图+最大流

题目大意：

　　John有n头牛，每头牛需要分配food和drink，food有F种，drink有D种，每种food和drink最多仅可以被分配一次，每头牛最多可以分配到一种food和一种drink，且每头牛有自己喜欢的food和drink，问最多有多少牛可以得到所期望的分配。

分析：

　　建立一个超级源点ST，ST向F个food分别连一条容量为1的边，表示每种food最多可以使用一次;

　　建立一个超级汇点ED，D个drink向ED分别连一条容量为1的边，表示每种drink最多可以使用一次;

　　根据牛的喜好，把牛和food，drink连一条容量为1的边;

　　考虑到每头牛最多可以被分配到一种food和一种drink，进行拆点，代表牛的点拆成两个点，且这两个点连一条容量为1的边，就限制了牛被分配到的food和drink最多分别有1种。

　　具体见代码。

　　然后用Edmonds_karp模版一次最大流即可。

代码：

poj3281

 1 /*3281    Accepted    904K    79MS    C++    1930B    2012-06-09 13:07:23*/
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <vector>
 8 using namespace std;
 9 
10 #define mpair make_pair
11 #define pii pair<int,int>
12 #define MM(a,b) memset(a,b,sizeof(a));
13 typedef long long lld;
14 typedef unsigned long long u64;
15 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;}
16 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;}
17 #define maxn 420
18 
19 int ST,ED;
20 int F,N,D;
21 int g[maxn][maxn];
22 
23 void Init(){
24     ST=0;
25     ED= F+N+N+D+1;
26     int i,tf,td,t;
27     MM( g, 0 );
28     for(i=1;i<=F;++i) g[0][i]= 1;
29     for(i=F+1;i<=F+N;++i) g[i][i+N]= 1;
30     for(i=F+N+N+1;i<=F+N+N+D;++i) g[i][ED]= 1;
31     for(i=F+1;i<=F+N;++i){
32         scanf("%d%d", &tf, &td);
33         while( tf-- ){
34             scanf("%d", &t);
35             g[t][i]= 1;
36         }
37         while( td-- ){
38             scanf("%d", &t);
39             g[i+N][F+N+N+t]= 1;
40         }
41     }
42 }
43 
44 const int inf= 2100000000;
45 bool vis[maxn];
46 int pre[maxn], que[maxn];
47 bool bfs(){
48     fill( vis+ST, vis+ED+1, 0 );
49     int head= 0, tail= 0;
50     que[tail++]= ST;
51     vis[ST]= 1;
52     while( head<tail ){
53         int u= que[head++];
54         for(int v= ST;v<=ED;++v){
55             if( g[u][v]>0 && !vis[v] ){
56                 pre[v]= u;
57                 if( v==ED ) return 1;
58                 vis[v]= 1;
59                 que[tail++]= v;
60             }
61         }
62     }
63     return 0;
64 }
65 
66 int Edmonds_karp(){
67     int ret= 0;
68     while( bfs() ){
69         int t= inf;
70         for(int i=ED;i!=ST;i=pre[i])
71             up_min( t, g[pre[i]][i] );
72         ret+= t;
73         for(int i=ED;i!=ST;i=pre[i])
74             g[pre[i]][i]-= t, g[i][pre[i]]+= t;
75     }
76     return ret;
77 }
78 
79 int main()
80 {
81     //freopen("poj3281.in","r",stdin);
82     while( cin>>N>>F>>D ){
83         Init();
84         int ans= Edmonds_karp();
85         cout<< ans <<endl;
86     }
87 }