题意：有n头牛，f种食物，d种饮料，每头牛有自己喜欢的食物和饮料，问你最多能够几头牛搭配好，每种食物或者饮料只能一头牛享用；
解题思路：把牛拆点，因为流过牛的流量是由限制的，只能为1，然后，食物和牛的入点相连，牛的出点和饮料相连，求解最大流
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=200500;
const int inf=0x3f3f3f3f;
struct Edge
{
int fa;
int next;
int to;
int w;
}edge[maxn];
int n,m,f,d;
int head[maxn];
int cnt,Start,End;
int x,y,w;
int depth[maxn];
void add(int u,int v,int w)
{
//cout<<u<<" "<<v<<endl;
edge[cnt].next=head[u];edge[cnt].fa=u;
edge[cnt].to=v;edge[cnt].w=w;head[u]=cnt++;
edge[cnt].next=head[v];edge[cnt].fa=v;
edge[cnt].to=u;edge[cnt].w=0;head[v]=cnt++;
}
bool bfs()//分层;
{
memset(depth,0,sizeof(depth));
queue<int>q;
q.push(Start);
depth[Start]=1;
while(!q.empty())
{
int temp=q.front();
q.pop();
for(int i=head[temp];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(depth[v]||edge[i].w<=0)
continue;
depth[v]=depth[temp]+1;
q.push(v);
}
}
return depth[End];//若为0表示没法到达也就是没有路径了；
}
int dfs(int u,int maxflow)
{
if(u==End)
return maxflow;
int add=0;
for(int i=head[u];i!=-1&&add<maxflow;i=edge[i].next)
{
int v=edge[i].to;
if(depth[v]!=depth[u]+1)
continue;
if(edge[i].w==0)
continue;
int tempflow=dfs(v,min(edge[i].w,maxflow-add));
edge[i].w-=tempflow;
edge[i^1].w+=tempflow;
add+=tempflow;
}
return add;
}
int dinic()
{
int ans=0;
while(bfs())
{
ans+=dfs(Start,0x3f3f3f3f);
}
return ans;
}
int main()
{
int tmp;
memset(head,-1,sizeof(head));
scanf("%d%d%d",&n,&f,&d);
Start=0;End=2*n+f+d+1;
for(int i=1;i<=n;i++)
add(i,i+n,1);
for(int i=2*n+1;i<=2*n+f;i++)
add(Start,i,1);
for(int i=2*n+f+1;i<=2*n+f+d;i++)
add(i,End,1);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
for(int j=1;j<=x;j++)
{
scanf("%d",&tmp);
add(tmp+2*n,i,1);
}
for(int j=1;j<=y;j++)
{
scanf("%d",&tmp);
add(i+n,tmp+2*n+f,1);
}
}
int ans=dinic();
printf("%d\n",ans);
}
原文：https://www.cnblogs.com/huangdao/p/9965896.html