学步园

类似于二分匹配，但不同的是，这次一头牛要匹配两样东西，食物和饮料

把每头牛拆成两个点，左边牛的左边连食物，右边牛的右边连饮料，源点与食物相连，饮料与汇点相连，每条边的容量都为1

这样，只有分配到食物的牛所代表的点，才会有流量流入饮料点，这样就保证流入汇点的流自某样食物经过某头牛到达某种饮料，即题目所要求的一头牛分配一样食物和一种饮料

代码：

#include<iostream><br /> using namespace std;<br /> int f[405][405],cap[405][405];<br /> int pre[405],rc[405],q[405];<br /> int n,F,d,maxx,ans;<br /> bool bfs()<br /> {<br /> int i,j,head=0,tail=1;<br /> memset(rc,0,sizeof(rc));<br /> pre[0]=-1;<br /> rc[0]=99999;<br /> q[tail]=0;<br /> while(head<tail)<br /> {<br /> i=q[++head];<br /> for(j=1;j<=maxx+1;j++)<br /> {<br /> if(cap[i][j]>f[i][j]&&!rc[j])<br /> {<br /> rc[j]=rc[i];<br /> if(cap[i][j]-f[i][j]<rc[j])<br /> rc[j]=cap[i][j]-f[i][j];<br /> pre[j]=i;<br /> q[++tail]=j;<br /> if(j==maxx+1)<br /> return true;<br /> }<br /> }<br /> }<br /> return false;<br /> }<br /> void update()<br /> {<br /> for(int i=maxx+1;i!=0;i=pre[i])<br /> {<br /> f[pre[i]][i]+=rc[maxx+1];<br /> f[i][pre[i]]=-f[pre[i]][i];<br /> }<br /> ans+=rc[maxx+1];<br /> }<br /> void EK()<br /> {<br /> while(bfs())<br /> update();<br /> }<br /> int main()<br /> {<br /> int i,j,k,a,b;<br /> while(scanf("%d%d%d",&n,&F,&d)!=EOF)<br /> {<br /> memset(f,0,sizeof(f));<br /> memset(cap,0,sizeof(cap));<br /> for(i=1;i<=F;i++)<br /> cap[0][i]=1;<br /> for(i=1;i<=n;i++)<br /> cap[i+F][i+F+n]=1;<br /> maxx=2*n+d+F;<br /> for(i=1;i<=n;i++)<br /> {<br /> scanf("%d %d",&a,&b);<br /> for(j=1;j<=a;j++)<br /> {<br /> scanf("%d",&k);<br /> cap[k][i+F]=1;<br /> }<br /> for(j=1;j<=b;j++)<br /> {<br /> scanf("%d",&k);<br /> cap[n+F+i][2*n+F+k]=1;<br /> cap[2*n+F+k][maxx+1]=1;<br /> }<br /> }<br /> ans=0;<br /> EK();<br /> printf("%d/n",ans);<br /> }<br /> return 0;<br /> }