【Poj 2112】 Optimal Milking

网络流博大精深！！！ 构图太巧妙了！

自己犯了几个错误！

• 1 bfs()没有初始化 head tail
• 2 Floyd 时 没有把没有边的 初始为INF！！ 这很重要！！！！！
• 3 bfs() 分层时 没有加mid的限制条件！！！
• 4 tmp=dfs(i,min(mmin,g[x][i]) 这一句 才开始 写成tmp=(i,min(mmin,g[x][i]) ......调试最耗时的一个错误！

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 100000000
using namespace std;

int k,c,m;
int a[250][250];
int n;

int s,t;
int g[250][250];
int d[250];
int team[250],head,tail;
int mid;

bool bfs()
{
	head=tail=0;  //!!!
	memset(d,0,sizeof(d));
	d[s]=1;
	team[++tail]=s;
	while(head<tail)
	{
		int x=team[++head];
		for(int i=1;i<=n;i++)
			if(d[i]==0&&g[x][i]!=0&&a[x][i]<=mid)
				d[i]=d[x]+1,team[++tail]=i;
	}
	if(d[t]==0) return false;
	else 		return true;
}
int dfs(int x,int mmin)
{
	int tmp;
	if(x==t) return mmin;
	for(int i=1;i<=n;i++)
		if(d[i]==d[x]+1&&g[x][i]&&a[x][i]<=mid&&(tmp=dfs(i,min(mmin,g[x][i]))))
		{
			g[x][i]-=tmp;
			g[i][x]+=tmp;
			return tmp;
		}
	return 0;
}
int main()
{

	scanf("%d %d %d",&k,&c,&m);n=k+c;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
			if(a[i][j]==0) a[i][j]=INF;  //!!!!! Floyd 要初始最大！ 
		}
			
	for(int kk=1;kk<=n;kk++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
					a[i][j]=min(a[i][j],a[i][kk]+a[kk][j]);

	s=n+1,t=n+2;
	int L=0,R=200*n;
	int OU;

	while(L<R)
	{
		memset(g,0,sizeof(g));
		for(int i=k+1;i<=n;i++) g[s][i]=1;
		for(int i=1;i<=k;i++) g[i][t]=m;
		for(int i=k+1;i<=n;i++)
			for(int j=1;j<=k;j++)
				if(a[i][j])
					g[i][j]=1;
		
		mid=(L+R)/2;
		int ans=0;
		n+=2;
		while(bfs()) ans+=dfs(s,INF);
		if(ans==c) OU=mid,R=mid;
		else L=mid+1;
		n-=2;
	}
	printf("%d\n",OU);
	return 0;
 }