记录编号	248848	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2016-04-11 15:57:37	内存使用	0.35 MiB

//KZNS
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;
//___________________
ifstream fin ("maxflowa.in");
ofstream fout ("maxflowa.out");
const int Nmax = 103;
//*******************
int N;
int gp[Nmax][Nmax];
int dp[Nmax];
////fds/afsd/af/f////
int DFS(int x, int mn) {
	if (x == N)
		return mn;
	for (int i = 1; i <= N; i++) {
		if (dp[i] == dp[x]+1 && gp[x][i]) {
			int u = DFS(i, min(mn, gp[x][i]));
			if (u) {
				gp[x][i] -= u;
				gp[i][x] += u;
				return u;
			}
		}
	}
	return 0;
}
////////main/////////
int main() {
	fin >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			fin >> gp[i][j];
	queue<int> ls;
	int ed = 0;
	while (true) {
		memset(dp, 0, sizeof (dp));
		dp[1] = 1;
		ls.push(1);
		while (!ls.empty()) {
			int u = ls.front();
			ls.pop();
			for (int i = 1; i <= N; i++) {
				if (gp[u][i] && (!dp[i])) {
					dp[i] = dp[u] + 1;
					ls.push(i);
				}
			}
		}
		if (!dp[N])
			break;
		int u;
		while (u = DFS(1, 0x7fffffff)) {
			ed += u;
		}
	}
	fout << ed;
	return 0;
}
//UBWH