记录编号	177876	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2015-08-12 20:41:17	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
int as[102][102],deep[102],flow,a;
int n,h;
bool bfs()
{
	queue<int>q;
	memset(deep,-1,sizeof(deep));
	deep[1]=1;
	q.push(1);
	while(!q.empty())
	{
		int yu=q.front();
		q.pop();
		for(int i=1;i<=n;++i)
		{
			if(as[yu][i]&&deep[i]<0)
			{
				deep[i]=deep[yu]+1;
				q.push(i);
			}
		}
	}
	if(deep[n]>0) return true;
	return false;
}
int find(int s,int low)
{  
	if(s==n) return low;
	for(int i=1;i<=n;++i)
	{
		if(deep[i]==deep[s]+1&&as[s][i])
		{
			if(a=find(i,min(low,as[s][i])))
			{
				as[s][i]-=a;
				as[i][s]+=a;
				return a;
			}
		}
	}
	return 0;
}
int main()
{   freopen("maxflowa.in" ,"r",stdin ) ;
	freopen("maxflowa.out","w",stdout) ;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	 for(int j=1;j<=n;++j)
	  scanf("%d",&as[i][j]);
	while(bfs())
	{
		while(h=find(1,9999999)) flow+=h;
	}
	printf("%d",flow);
}