记录编号	34770	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2012-01-03 13:47:16	内存使用	0.31 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;

const int INF=0x7ffffff; 
const int MAXN=101;
int Map[MAXN][MAXN];
int Father[MAXN];
bool Used[MAXN];
int Ans;
int N,M;
int S,T;

void Ford_Fulkerson()
{
	while(1)
	{
		queue<int>Q;
		memset(Used,0,sizeof(Used));
		memset(Father,0,sizeof(Father));
		
		int now;
		Used[S]=true;
		Q.push(S);
		while(!Q.empty())
		{
			now=Q.front();
			Q.pop();
			if(now==T)
				break;
			for (int i=1;i<=N;i++)
			{
				if(Map[now][i] && !Used[i])
				{
					Father[i]=now;
					Used[i]=true;
					Q.push(i);
				}
			}
		}
		
		if(!Used[T])// There is no Augmenting Path.
			break;
		
		int u;
		int Min=INF;
		for (u=T;u!=S;u=Father[u])
		{
			if(Map[Father[u]][u]<Min)
				Min=Map[Father[u]][u];
		}
		
		for (u=T;u!=S;u=Father[u])
		{
			Map[Father[u]][u]-=Min;
			Map[u][Father[u]]+=Min;
		}
		
		Ans+=Min;
	}
}


void init()
{
	scanf("%d\n",&N);
	M=0;
	memset(Map,0,sizeof(Map));
	
	int v;
	for (int i=1;i<=N;i++)
	{
		for (int j=1;j<=N;j++)
		{
			scanf("%d",&v);
			Map[i][j]=v;
			if(v)
				M++;
		}
	}
	S=1;
	T=N;
	return;
}

int main()
{
	freopen("maxflowa.in","r",stdin);
	freopen("maxflowa.out","w",stdout);
	init();
	Ford_Fulkerson();
	printf("%d\n",Ans);
	return 0;
}