记录编号	397579	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	Jobs.T	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-04-20 18:58:24	内存使用	0.00 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
 
int n;
class edge{
  public:
	  int fr, to, v, ne;
}e[12345];
int head[105], tot;
int dis[105];
int s, t;
 
inline void addedge(int a, int b, int v) {
	e[++tot].fr = a;
	e[tot].to = b;
	e[tot].ne = head[a];
	e[tot].v = v;
	head[a] = tot;
	e[++tot].fr = b;
	e[tot].to = a;
	e[tot].ne = head[b];
	head[b] = tot;
}
 
inline bool bfs() {
	queue <int> q;
	q.push(s);
	memset(dis, 0, sizeof(dis));
	dis[1] = 1;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = head[now]; i; i = e[i].ne) {
			int to = e[i].to;
			if ((!dis[to] || dis[to] == dis[now] + 1) && e[i].v) {
				dis[to] = dis[now] + 1;
				q.push(to);
			}
		}
	}
	return dis[t];
}
 
int dfs(int now, int min_flow) {
	int now_flow;
	if (now == t) {
		return min_flow;
	}
	for (int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if (dis[to] != dis[now] + 1) continue;
		if (!e[i].v) continue;
		now_flow = dfs(to, min(min_flow, e[i].v));
		if (!now_flow) continue;
		e[i].v -= now_flow;
		if (i % 2) e[i + 1].v += now_flow;
		else e[i - 1].v += now_flow;
		return now_flow;
	}
	return 0;
}
 
int dinic() {
	int ans = 0;
	int tmp;
	while (bfs()) {
		while (tmp = dfs(s, 21474836)) ans += tmp;
	}
	return ans;
}
 
int Main() { 
#ifndef LOCAL
	freopen("maxflowa.in", "r", stdin);
	freopen("maxflowa.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int tmp;
			scanf("%d", &tmp);
			if (tmp) addedge(i, j, tmp);
		}
	}
	s = 1;
	t = n;
	int ans = dinic();
	printf("%d\n", ans);
	return 0;
}

int AA = Main();

int main() {;}