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

/*kZime*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define MAXN 233
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, dis[MAXN], ans, en, head[MAXN], ma[MAXN][MAXN];

struct edge{
	int fr, to, ne, v;
	
	edge() {}
	edge(int fr_, int to_, int ne_, int v_) { fr = fr_, to = to_, ne = ne_, v = v_; }
} e[MAXN * MAXN];

inline void add_edge(int fr, int to, int v, int inv_v) {
	e[++en] = edge(fr, to, head[fr], v), head[fr] = en;
	e[++en] = edge(to, fr, head[to], inv_v), head[to] = en;
}

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 = head[x]; i; i = e[i].ne) {
			int y = e[i].to;
			if(dis[y] < 0 && e[i].v > 0){
                  dis[y] = dis[x] + 1; 
                  q.push(y);
            }
		}
	}
	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 = head[x]; i; i = e[i].ne){
    	int y = e[i].to;
    	if(e[i].v > 0 && dis[y] == dis[x] + 1 && (a = dfs(y, min(low, e[i].v)))) {
    	   e[i].v -= a;
    	   (i & 1) ? (e[i + 1].v += a) : (e[i - 1].v += a);
    	   return a;
    	}
	}
	
	for(int i = head[x]; i; i = e[i].ne) {
		int y = e[i].to;
		
	}
	
    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++) {
			ma[i][j] = read();
		}
	}
	
	for(int i = 1; i <= n; i++) {
		for(int j = i + 1; j <= n; j++) {
			add_edge(i, j, ma[i][j], ma[j][i]);
		}
	}
	
	
	while(bfs()) {
		int tans = 0;
		while(tans = dfs(1, 0x7fffffff)) {
			ans += tans;
		}
	}
	
	printf("%d", ans);
	
	return 0;
}
int HA = AC();
int main(){;}