昨晚躺在床上想这题怎么构图呢....
开始的时候想的是源点到牛的流量为2(限制牛只能吃1喝1)。再而牛与吃喝直接连边,容量为1.吃喝拆开成两个两两直接连边,容量为1,保证每个吃喝只有一次。再末端吃喝连边到汇点。这种想当然的思路我竟然开始敲了代码!!真是...
上面的构图有明显的错误,因为牛可以吃2个或者喝2个,这是我的图不能控制的。
转而想... 将每头牛拆成3只,一头容量限制容量为2,一头管吃一头管喝... so... 这样虽然可以限制只吃喝一次,但是呢... 却不能满足让牛吃与喝,因为这么流过去,到汇点相关的就只有吃与喝了,这样计算的只是吃喝尽量被消耗,可能一头牛只喝或只吃,汇点却不会管这些。
睡觉前,终于把构图想通了。
源点与吃相连,吃与牛相连,牛与牛'相连,牛'与喝相连,喝与源点相连。这么一波流过去,保证了牛有吃又有喝。
具体为什么?感觉......竟然还RE了,因为少了个EOF...
#include<iostream>
#include<cstdio>
#include<string>
#define MN 444
using namespace std;int map[MN][MN],pre[MN],que[MN],a[MN],vis[MN];
int n,f,d,fi,di,ans,s,t;void setG()
{int i,j,k;memset( map,0,sizeof(map) );ans=0;s=0;t=2*n+f+d+1;for( i=1;i<=n;i++ ){scanf( "%d%d",&fi,&di );for( j=1;j<=fi;j++ ){scanf( "%d",&k );map[n*2+k][i]=1;}for( j=1;j<=di;j++ ){scanf( "%d",&k );map[n+i][n*2+f+k]=1;}map[i][n+i]=1;}for( i=2*n+1;i<=2*n+f;i++ )map[s][i]=1;for( i=2*n+f+1;i<=2*n+f+d;i++ )map[i][t]=1;
}bool bfs()
{memset( vis,0,sizeof(vis) );int head=0,foot=0;que[foot++]=s;vis[s]=true;a[s]=INT_MAX;while( head<foot ){int u=que[head++];for( int i=0;i<=t;i++ ){if( !vis[i]&&map[u][i] ){a[i]=min(a[u],map[u][i]);pre[i]=u;if( i==t )return true;vis[i]=true;que[foot++]=i;}}}return false;
}void work()
{while( bfs() ){int m=t;ans+=a[t];while( m!=s ){map[pre[m]][m]-=a[t];map[m][pre[m]]+=a[t];m=pre[m];}}printf( "%d\n",ans );
}int main()
{while( scanf("%d%d%d",&n,&f,&d)!=EOF ){setG();work();}return 0;
}