[文章目录]
Descripiton
农夫JOHN做了F (1 <= F <= 100) 种食品并准备了D (1 <= D <= 100) 种饮料. 他的N (1 <= N <= 100)头牛都以决定了是否愿意吃某种食物和喝某种饮料. 农夫JOHN想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物和饮料.
如果只有食物的话好说。直接二分图。
如果有两个的话。可以将牛的集合放到中间并进行限流，然后两边是食物和饮料。最大流即为答案。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,ff,d,s,t,ans;
int head[500],to[60000],nxt[60000],f[60000],cnt=1;
void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
int dis[500];
queue<int>q;
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-1,sizeof dis);
dis[s]=0; q.push(s); int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]<0)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i])
if(f[i]&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d%d%d",&n,&ff,&d);
int i,j,x,y,z; s=ff+2*n+d+1,t=s+1;
for(i=1;i<=n;++i)
{
scanf("%d%d",&x,&y);
while(x--)
{
scanf("%d",&z);
add(z,ff+i,1);
}
while(y--)
{
scanf("%d",&z);
add(ff+n+i,ff+2*n+z,1);
}
}
for(i=1;i<=n;i++) add(ff+i,ff+n+i,1);
for(i=1;i<=ff;i++) add(s,i,1);
for(i=2*n+ff+1;i<=2*n+ff+d;i++) add(i,t,1);
while(bfs()) ans+=dinic(s,1<<30);
printf("%d",ans);
return 0;
}