pku 3281 最大流建图

http://acm.pku.edu.cn/JudgeOnline/problem?id=3281

建一个图

把牛分成两排，左边一排跟食物，，右边一排跟饮料相连，，食物左边跟源点，，饮料右边跟汇点，，

两排牛相对应的牛再连一条线，，图中连的线的权重都为 1 ，，求最大流

刚开始的时候只用了一排牛。。WA啦

百度了下，看到要用两排牛。试着改成两排牛,,就 AC 了，，

具体原因，，其实画个图就明白了

因为牛也最多只能进入一次，出去一次，，所以如果只有一排的话，无法限制牛点的度

所以如果把牛弄成两个点，，中间只有一条路，，那么理所当然的，牛最多只能进去一次，，出来一次，，OK

PERFECT

不过我的猥琐代码超了很多，，

等待更新哦，（、、、、

#include<iostream>
#define Nmax 424
#define INF 1000000
using namespace std; 
int col[Nmax][Nmax],n;
int Min(int a,int b)
{
	return a<b?a:b;
}
int Get_Max(int source ,int sink)
{
	int flow[Nmax][Nmax],pre[Nmax],queue[Nmax],i,j,u,min[Nmax],rest,ans,t,k;
	for(i=0;i<=n;i++)for(j=0;j<=n;j++)flow[i][j]=0;
	while(1)
	{
		for(i=0;i<=n;pre[i++]=0);
		pre[u=source]=u;
		min[u]=INF;
		for(k=1,t=1;!pre[sink]&&k<=t;u=queue[k++])//广搜
		{
			for( i=1;i<=n;i++)
			{
				if(pre[i]==0 && col[u][i]-flow[u][i]>0)
				{
					rest=col[u][i]-flow[u][i];
					queue[t++]=i;//入队列
					pre[i]=u;
					min[i]=Min(min[u],rest);
				}
				else if(pre[i]==0 && flow[i][u]>0)
				{
					queue[t++]=i;
					pre[i]=-u;
					min[i]=Min(min[u],flow[i][u]);
				}
			}
		
		}
	//	cout<<min[sink]<<endl;
		if(pre[sink]==0)break;
		for(i=sink;i!=source;)
		{
			if(pre[i]>0)
			{
				flow[pre[i]][i]+=min[sink];
				i=pre[i];
			}
			else
			{
				flow[i][-pre[i]]-=min[sink];
				i=-pre[i];
			}
		}
	}
	for (ans=0,i=1; i<=n;i++)ans+=flow[source][i];//从源点流出，与源点相连的点的和。。
	return ans;
}

int main()
{
	freopen("input.txt","r",stdin);
	int N,f,c,i,j;
	while(scanf("%d%d%d",&N,&f,&c)!=EOF)
	{
		n=N+f+c+2+N;
		for( i =0; i<= n; i ++)
			 for ( j =0 ;j <= n ; j++ )col[i][j]=0;
		for(i = 2; i <= f+1; i++) col[1][i]=1;
		for(i = n-1 ; i >= n-c ; i --)col[i][n]=1;

		for(i=f+2;i< n-c-N;i++)
		{
			int a,b,x,y,k;
			scanf("%d%d",&a,&b);
			for(j=0;j<a;j++)
			{
				scanf("%d",&x);
				col[x+1][i]=1;
			}
			int t =1+f+N+N;
			for(k=0;k<b;k++)
			{
			
				scanf("%d",&y);
				col[i+N][y+t]=1;
			}
			col[i][i+N]=1;
		}
			
		cout<<Get_Max(1,n)<<endl;
	}
	return 0;
}

）

pku 3281 最大流 建图

pku 3281 最大流建图