将牛拆为两个点.
原点向食物连边,食物向牛1连边,牛1向牛2连边,牛2向饮料连边,跑最大流即可
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define MAXN 1010
#define INF 1000000
using namespace std;
int N,F,D,ecnt=1,k1,k2,S,T,x,tmp,lev[MAXN],ans,head[MAXN];
queue <int> q;
struct adj
{
int u,v,w;
}e[10*MAXN];
void add(int u,int v,int w)
{
e[++ecnt].v=v;
e[ecnt].w=w;
e[ecnt].u=head[u];
head[u]=ecnt;
}
int bfs()
{
memset(lev,-1,sizeof(lev));
lev[S]=0;
q.push(S);
while (!q.empty())
{
int x=q.front();
for (int i=head[x];i;i=e[i].u)
{
int v=e[i].v;
if (lev[v]==-1 && e[i].w>0)
lev[v]=lev[x]+1,q.push(v);
}
q.pop();
}
return lev[T]!=-1;
}
int dfs(int x,int flw)
{
if (x==T) return flw;
for (int i=head[x];i;i=e[i].u)
{
int v=e[i].v,tmp;
if (lev[v]==lev[x]+1 && e[i].w>0 && (tmp=dfs(v,min(flw,e[i].w)))>0)
{
e[i].w-=tmp;
e[i^1].w+=tmp;
return tmp;
}
}
return 0;
}
int main()
{
scanf("%d%d%d",&N,&F,&D);
S=F+D+2*N+1,T=F+D+2*N+2;
for (int i=1;i<=N;i++)
add(i,N+i,1),add(i+N,i,0);
for (int i=1;i<=N;i++)
{
scanf("%d%d",&k1,&k2);
while (k1--)
scanf("%d",&x),add(x+2*N,i,1),add(i,x+2*N,0);
while (k2--)
scanf("%d",&x),add(i+N,2*N+F+x,1),add(2*N+F+x,i+N,0);
}
// printf("READ OVER
");
for (int i=1;i<=F;i++)
add(S,i+2*N,1),add(i+2*N,S,0);
for (int i=1;i<=D;i++)
add(2*N+F+i,T,1),add(T,2*N+F+i,0);
while (bfs())
while ((tmp=dfs(S,INF))>0) ans+=tmp;
printf("%d",ans);
return 0;
}