POJ 3281 Dining 网络流
题意：
给出N,F,D。表示N头牛，F种食物，D种饮料。
接下来2-N+1行，输入n,m代表第i头牛喜欢的食物种类为n,饮料种类为m。接下来输入n个数，代表食物的编号，输入m个数，代表饮料的编号。
输出最多能满足多少头牛吃上喜欢的食物和饮料。
思路：
将牛拆成2个点，左边为食物，右边为饮料。
s---食物---牛---牛----饮料---e.
每条边的限制流量为1.
#include <iostream>#include <cstdio>#include <algorithm>#include <string>#include <cmath>#include <cstring>#include <queue>#include <set>#include <vector>#include <stack>#include <map>#include <iomanip>#define PI acos(-1.0)#define Max 1005#define inf 1<<28#define LL(x) (x<<1)#define RR(x)(x<<1|1)using namespace std;int N,F,D;int cow[Max][Max];int path[Max];int flow[Max];int start,end;int q[Max*100];int bfs(){ memset(path,-1,sizeof(path)); flow[0]=inf; //queue<int>q; int num=0,cnt=0; path[0]=0; q[num++]=0; while(num>cnt) { int temp=q[cnt++]; if(temp==end) break; for(int i=1; i<=end; ++i) { if(path[i]==-1&&cow[temp][i]) { flow[i]=min(flow[temp],cow[temp][i]); q[num++]=i; path[i]=temp; } } } if(path[end]==-1)return -1; else return flow[end];}int EK(){ int max_flow=0,pre,step; while((step=bfs())!=-1) { int now=end; max_flow+=step; while(now!=start) { pre=path[now]; cow[pre][now]-=step; cow[now][pre]+=step; now=pre; } } return max_flow;}int main(){ int i,j,k,l,n,m; int f,d; while(scanf("%d%d%d",&N,&F,&D)!=EOF) { int tt; start=0,end=F+N+D+N+1;//超级源点0，超级汇点F+N+D+N+1; for(i=1; i<=F; i++)//连接源点到所有的食物，流量为1; cow[0][i]=1; for(i=1; i<=N; ++i) { scanf("%d%d",&f,&d); n=f,m=d; while(n--) { scanf("%d",&tt); cow[tt][i+F]=1; } while(m--) { scanf("%d",&tt); cow[i+F+N][tt+F+N+N]=1; cow[tt+F+N+N][end]=1;//连接所有饮料到汇点，流量为1; } } for(i=1; i<=N; ++i) cow[i+F][i+F+N]=1;//连接拆开的2头牛 printf("%d\n",EK()); } return 0;}