POJ 3281 Dining (巧妙建图+最大流)

http://poj.org/problem?id=3281
题意：Farmer John有$N$头牛，$F$个食物，$D$个饮料。每头牛只喜欢某几种食物和某几种饮料。每个食物和饮料只能给一头牛，一头牛只能得到一个食物和饮料。而且一头牛必须同时获得喜欢的食物和喜欢的饮料才能满足。问至多有多少头牛可以获得满足。

一眼看不出是最大流问题，但是可以通过巧妙的建图转化成最大流问题，具体方法如下：
将每头牛分成两个点，一个点与喜欢的食物连边，一个点与喜欢的饮料连边，两个点之间再连一条容量为1的边，这样就可以保证每头牛都只选一个食物和一个饮料。然后所有食物与一个超级源点相连，所有饮料与一个超级汇点相连，连成一个像下面这样的图。

还要稍微注意的一点是编号问题，具体根据自己的习惯就好，我的编号方法是超级源点为$0$，食物是$1～ F$，牛的第一个点是$F+1～F+N$，牛的第二个点是$F+N+1～F+N+N$，饮料是$F+N+N+1～F+N+N+D$，超级汇点是$F+N+N+D+1$，具体看代码注释吧。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define INF 0x3f3f3f
using namespace std;const int maxn=100100;
int head[maxn],dis[maxn],k,n,D,F;
struct edge{int v,c,next;
}e[maxn];
void addedge(int u,int v,int c)
{e[k].v=v;e[k].c=c;e[k].next=head[u];head[u]=k++;e[k].v=u;e[k].c=0;e[k].next=head[v];head[v]=k++;
}int bfs(int s,int t)
{memset(dis,0,sizeof(dis));dis[s]=1;queue<int> q;q.push(s);while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].v;if(!dis[v]&&e[i].c){dis[v]=dis[u]+1;if(v==t) return 1;q.push(v);}}}return 0;
}int dfs(int u,int a,int t)
{if(u==t) return a;int res=0;for(int i=head[u];i!=-1;i=e[i].next){if(!a) break;int v=e[i].v;if(e[i].c&&dis[v]==dis[u]+1){int f=dfs(v,min(a,e[i].c),t);if(f>0){e[i].c-=f;e[i^1].c+=f;res+=f;a-=f;}elsedis[v]=-1;}}return res;
}int dinic(int s,int t)
{int res=0;while(bfs(s,t)){res+=dfs(s,INF,t);}return res;
}int main()
{int x,y,a,b;while(~scanf("%d%d%d",&n,&F,&D)){memset(head,-1,sizeof(head));for(int k=1;k<=n;k++){scanf("%d%d",&x,&y);for(int i=1;i<=x;i++){scanf("%d",&a);addedge(a,k+F,1);//食物与牛的第一个点连边}for(int i=1;i<=y;i++){scanf("%d",&b);addedge(k+F+n,b+F+n+n,1);//牛的第二个点与饮料连边}addedge(k+F,k+F+n,1);//牛的第一个点与第二个点连边}for(int i=1;i<=F;i++)addedge(0,i,1);//食物与超级源点连边for(int i=1;i<=D;i++)addedge(i+F+n+n,F+n+n+D+1,1);//饮料与超级汇点连边printf("%d\n",dinic(0,F+n+n+D+1));}return 0;
}