记录编号	338317	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	Tiny	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2016-11-05 09:55:53	内存使用	90.47 MiB

#include <stdio.h>
#include <string.h>
#include <queue>

const size_t MAXS = 100 * 1024 * 1024;
int buf_cnt = 0;
char read_buf[MAXS];

template <typename T> inline void Read_buf(T &num) {
	num = 0; bool minus = false;
	while (read_buf[buf_cnt] < '-' || read_buf[buf_cnt] > '9') ++buf_cnt;
	if (read_buf[buf_cnt] == '-') { minus = true; ++buf_cnt; }
	while (read_buf[buf_cnt] >= '0' && read_buf[buf_cnt] <= '9')
		num = num * 10 + read_buf[buf_cnt++] - '0';
	if (minus) num = -num;
}

#define Min(a, b) ((a) < (b) ? (a) : (b))

#define INF 0x7f7f7f7f
const size_t MAXN = 200 + 11, MAXM = 10000 + 10;

struct Network_Flow {
	int S, T;
	struct Edge { int v, c, ne; } E[MAXM << 1];
	int head[MAXN], tot_e;
	int dis[MAXN];
	int Q[MAXN], front, tail;

	inline void BFS() {
		memset(dis, -1, sizeof (dis));
		front = 1; tail = 0;
		Q[++tail] = S; dis[S] = 0;
		for (; front - 1 != tail; ++front %= MAXN)
			for (int i = head[Q[front]]; i; i = E[i].ne)
				if (dis[E[i].v] == -1 && E[i].c) {
					Q[++tail %= MAXN] = E[i].v;
					dis[E[i].v] = dis[Q[front]] + 1;
				}
	}

	inline int DFS(const int &u, int delta) {
		if (u == T) return delta;
		int ret = 0;
		for (int i = head[u], t; delta && i; i = E[i].ne)
			if (E[i].c && dis[E[i].v] == dis[u] + 1) {
				t = DFS(E[i].v, Min(E[i].c, delta));
				E[i].c -= t; E[i ^ 1].c += t;
				delta -= t; ret += t;
			}
		return ret;
	}

public:
	inline Network_Flow() {}

	inline void Init() {
		tot_e = 1;
		memset(head, 0, sizeof (head));
		memset(E, 0, sizeof (E));
	}

	inline void Insert(const int &u, const int &v, const int &c) {
		E[++tot_e] = (Edge){ v, c, head[u] }; head[u] = tot_e;
		E[++tot_e] = (Edge){ u, 0, head[v] }; head[v] = tot_e;
	}

	inline int Max_Flow(const int &s, const int &t) {
		S = s; T = t;
		int ret = 0;
		while (1) {
			BFS();
			if (dis[T] == -1) return ret;
			ret += DFS(S, INF);
		}
	}

	inline ~Network_Flow() {}
} NF;

int main() {
 #define SUBMIT
 #ifdef SUBMIT
	freopen("maxflowa.in", "r", stdin);
	freopen("maxflowa.out", "w", stdout);
	fread(read_buf, 1, MAXS, stdin);
 #endif

	int n; Read_buf(n);
	NF.Init();
	for (int i = 1, t; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			Read_buf(t);
			if (t) NF.Insert(i, j, t);
		}
	}
	printf("%d\n", NF.Max_Flow(1, n));

 #ifndef SUBMIT
	puts("\n--------------------");
	getchar(); getchar();
 #else
	fclose(stdin); fclose(stdout);
 #endif
	return 0;
}