|
|
 #include <iostream>
using namespace std;
#define maxn 401
int g[maxn][maxn];//容量
int f[maxn][maxn];//流量
int r[maxn][maxn];//残量
int Edmonds_Karp(int g[][maxn],int s,int t,int f[][maxn])
   {
 int i,j,k,c,head,tail,flow=0 ;
int prev[maxn],visit[maxn],q[maxn];
for(i=s;i<=t;i++)for(j=s;j<=t;j++)
  {
f[i][j]=0 ;
r[i][j]=g[i][j];
 }
while(1)
{
head=tail=0 ;
memset(visit,0,sizeof(visit));
q[tail++]=s ;
prev[s]=-1 ;
visit[s]=1 ;
while(head<tail)
{
k=q[head++];
for(i=s;i<=t;i++) //注意修改
if(!visit[i]&&r[k][i]>0)
{
visit[i]=1 ;
prev[i]=k ;
if(i==t)goto next ;
q[tail++]=i ;
}
}
next :
if(!visit[t])break ;
for(c=INT_MAX,j=t;j!=s;j=i)
{
i=prev[j];
if(c>r[i][j])c=r[i][j];
}
for(j=t;j!=s;j=i)
{
i=prev[j];
f[i][j]+=c ;
f[j][i]=-f[i][j];
r[i][j]=g[i][j]-f[i][j];
r[j][i]=g[j][i]-f[j][i];
}
flow+=c ;
}
return flow ;
 }
int main()
{
int i,j;
int s,t;
int F,N,D;
scanf("%d%d%d",&N,&F,&D);
s=0;
t=F+N+N+D+1;
for(i=1;i<=N;i++)
{
int m,n,k;
scanf("%d%d",&m,&n);
for(j=1;j<=m;j++)//Food->Cow
{
scanf("%d",&k);
g[k][i+F]=1;
}
for(j=1;j<=n;j++)//Cow->Drink
{
scanf("%d",&k);
g[i+F+N][k+F+N+N]=1;
}
}
for(i=1;i<=F;i++)//Sourse->Food
g[s][i]=1;
for(i=1;i<=N;i++)//Cow->Cow
g[F+i][F+N+i]=1;
for(i=1;i<=D;i++)//Drink->Terminal
g[i+F+N+N][t]=1;
printf("%d\n",Edmonds_Karp(g,s,t,f));
return 0;
}
|