bzoj1711[Usaco2007 Open]Dining吃饭*

bzoj1711[Usaco2007 Open]Dining吃饭

题意：

每头牛都喜欢几种食品和饮料，现在每种食品和饮料都有一个，问最多能使多少头牛同时获得喜欢的食品和饮料。牛数、饮料数、食品数≤500

题解：

最大流，源向所有食品连边，食品向被喜欢的牛连边，牛向喜欢的饮料连边，饮料向汇连边，流量都为1。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 10000
 7 #define INF 0x3fffffff
 8 using namespace std;
 9 
10 inline int read(){
11     char ch=getchar(); int f=1,x=0;
12     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
13     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
14     return f*x;
15 }
16 struct e{int t,c,n;}; e es[maxn*2]; int g[maxn],ess;
17 void pe(int f,int t,int c){
18     es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,0,g[t]}; g[t]=ess;
19 }
20 void init(){memset(g,-1,sizeof(g)); ess=-1;}
21 queue<int>q; int h[maxn];
22 bool bfs(int s,int t){
23     while(!q.empty())q.pop(); memset(h,-1,sizeof(h)); h[s]=0; q.push(s);
24     while(!q.empty()){
25         int x=q.front(); q.pop();
26         for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==-1)h[es[i].t]=h[x]+1,q.push(es[i].t);
27     }
28     return h[t]!=-1;
29 }
30 int dfs(int x,int t,int f){
31     if(x==t)return f; int u=0;
32     for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&h[es[i].t]==h[x]+1){
33         int w=dfs(es[i].t,t,min(f,es[i].c)); f-=w; u+=w; es[i].c-=w; es[i^1].c+=w; if(!f)return u;
34     }
35     if(!u)h[x]=-1; return u;
36 }
37 int dinic(int s,int t){int flow=0; while(bfs(s,t))flow+=dfs(s,t,INF); return flow;}
38 int n,f,d,s,t;
39 int main(){
40     n=read(); f=read(); d=read(); s=0; t=f+n*2+d+1; init();
41     inc(i,1,n){
42         pe(f+i,f+n+i,1);
43         int a=read(),b=read();
44         inc(j,1,a){int c=read(); pe(c,f+i,1);}
45         inc(j,1,b){int c=read(); pe(f+n+i,f+n*2+c,1);}
46     }
47     inc(i,1,f)pe(s,i,1); inc(i,1,d)pe(f+n*2+i,t,1); printf("%d",dinic(s,t)); return 0;
48 }

20160809