POJ3281--Dining（最大流）

主要是构图。

刚开始我想的是源点->牛->食物->饮料，发现问题很多，正确的构图应该是源点->食物->牛->牛->饮料->汇点，中间牛与牛之间的容量为1。

#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<iostream>
using namespace std;

const int maxn=1005;
const int INF=999999999;

int n,m,F,D;
int f[maxn][maxn];
int pre[maxn];
int vis[maxn];

void Max_Flow()
{
	int t,i,temp,sum=0;
	while(1)
	{
		queue<int> q;
		memset(vis,0,sizeof(vis));
		memset(pre,0,sizeof(pre));
		vis[0]=1;
		q.push(0);
		while(!q.empty())
		{
			t=q.front();
			q.pop();
			if(t==n+n+D+F+1)
				break;
			for(i=0;i<=n+n+F+D+1;i++)
			{
				if(!vis[i] && f[t][i]>0)
				{
					vis[i]=1;
					q.push(i);
					pre[i]=t;
				}
			}
		}
		if(!vis[n+n+D+F+1])
			break;
		temp=INF;
		for(i=n+n+F+D+1;i!=0;i=pre[i])
		{
			if(temp>f[pre[i]][i])
				temp=f[pre[i]][i];
		}
		for(i=n+n+F+D+1;i!=0;i=pre[i])
		{
			f[pre[i]][i]-=temp;
			f[i][pre[i]]+=temp;
		}
		sum+=temp;
	}
	printf("%d\n",sum);
}

int main()
{
	while(scanf("%d%d%d",&n,&F,&D)!=EOF)
	{
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++)
		{
			int a,b,p;
			scanf("%d%d",&a,&b);
			for(int j=1;j<=a;j++)
			{
				scanf("%d",&p);
				f[0][p]=1;          //源点->食物
				f[p][F+i]=1;		//食物->牛
			}
			f[F+i][F+n+i]=1;        //牛->牛
			for(int j=1;j<=b;j++)
			{
				scanf("%d",&p);
				f[F+n+i][F+n+n+p]=1;     //牛->饮料
				f[F+n+n+p][F+n+n+D+1]=1; //饮料->汇点
			}
		}
		Max_Flow();
	}
	return 0;
}

POJ3281--Dining（最大流）

原文：http://blog.csdn.net/mfmy_szw/article/details/19087435