题目
题意：有N头奶牛，有F种食物，D种饮料，每头奶牛有自己喜欢的食物和饮料。问能让多少头奶牛满意。
题解： 画出图来这个题就简单很多了。 样例： （嘿嘿，food和cow以及cow和drink之间的太多了就没画） 把食物标号+100存下来，奶牛本身不变，但是要再加上一列奶牛标号+200（为了保证每头奶牛只被使用1次）然后饮料+300，然后从0-505找最大流。
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int maxn=555; const int inf=0x3f3f3f3f; int r[maxn][maxn]; bool visit[maxn]; int pre[maxn]; bool bfs(int s,int t) //寻找一条从s到t的增广路，若找到返回true { int p; queue<int > q; memset(pre,-1,sizeof(pre)); memset(visit,false,sizeof(visit)); pre[s]=s; visit[s]=true; q.push(s); while(!q.empty()) { p=q.front(); q.pop(); if(p==t) return true; for(int i=1;i<=t;i++) { if(r[p][i]>0&&!visit[i]) { pre[i]=p; visit[i]=true; //if(i==t) return true; q.push(i); } } } return false; } int EdmondsKarp(int s,int t)//更新边的容量 { int flow=0,d,i; while(bfs(s,t)) { d=inf; for(i=t;i!=s;i=pre[i]) d=min(d,r[pre[i]][i]); for(i=t;i!=s;i=pre[i]) { r[pre[i]][i]-=d; r[i][pre[i]]+=d; } flow+=d; } return flow; } int main() { int m,n,f,d; while (~scanf("%d %d %d",&n,&f,&d)) { memset(r,0,sizeof r); for (int i = 1;i <= f;i++) { r[0][100 + i] = 1; } for (int i = 1;i <= d;i++) { r[300 + i][505] = 1; } for (int i = 1;i <= n; i++) { int tempf,tempd,temp; scanf("%d %d",&tempf,&tempd); for (int j = 0;j < tempf; j++) { scanf("%d",&temp); r[temp + 100][i] = 1; } for (int j = 0;j < tempd; j++) { scanf("%d",&temp); r[200 + i][300 + temp] = 1; } r[i][200+i]=1; } printf("%d\n",EdmondsKarp(0,505)); } return 0; }