记录编号	384160	评测结果	AAAAAAAAAA
题目名称	11.运输问题1	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-03-17 16:37:57	内存使用	0.00 MiB

/*kZime*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define MAXN
using namespace std;
inline int read() {
	int k = 0, f = 1; char c = getchar();
	for(; !isdigit(c); c = getchar())if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}
/*-----------------------------------------------------------------------------*/

int n, m, en, tab[233][233], dis[233], ans;

bool bfs() {
	memset(dis, -1, sizeof(dis));
	queue <int> q;
	q.push(1);
	dis[1] = 0;
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		for(int i = 1; i <= n; i++) {
			if(dis[i] < 0 && tab[x][i] > 0){
                  dis[i]=dis[x]+1; 
                  q.push(i);
            }
		}
	}
	if(dis[n] > 0) return 1;
	else return 0;
}

int dfs(int x, int low) {
    int a = 0;
    if(x == n)return low;
    for(int i = 1; i <= n; i++){
    	if(tab[x][i] > 0 && dis[i] == dis[x] + 1 && (a = dfs(i, min(low, tab[x][i])))) {
    	   tab[x][i] -= a;
    	   tab[i][x] += a;
    	   return a;
    	}
	}
    return 0;
} 

int AC() {
	freopen("maxflowa.in", "r", stdin);
	freopen("maxflowa.out", "w", stdout);
	n = read();
	
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			int z = read();
			tab[i][j] += z;
		}
	}
	
	while(bfs()) {
		int tans = 0;
		while(tans = dfs(1, 0x7fffffff)) {
			ans += tans;
		}
	}
	
	printf("%d", ans);
	
	return 0;
}
int HA = AC();
int main(){;}