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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

#define is_num(tmp) (tmp<='9' and tmp>='0')
#define MAXN 110
#define INF 0x7ffffff

const inline int in(void){
	char tmp = getchar();
	int res = 0;
	while(!is_num(tmp))tmp = getchar();
	while(is_num(tmp))
		res = (res<<1) + (res<<3) + (tmp^48),
		tmp = getchar();
	return res;
}

class Max_flow{
private:
	struct EDGE{
		int to, ne;
		int v, rv;
		
		EDGE(){;}
		EDGE(const int& a, const int& b, const int& c){
			to = a, ne = b, v = c, rv = 0;
		}
	};
	EDGE edge[MAXN * MAXN];
	int head[MAXN], tot;
	const inline void add_edge(const int& fr, const int& to, const int& v){
		edge[++tot] = EDGE(to, head[fr], v), head[fr] = tot;
		return ;
	}
	
	int N, S, T;
	queue<int>que;
	int deep[MAXN];
	int res;
	
	bool bfs(void){
		memset(deep, 0, sizeof(deep));
		deep[S] = 1;
		while(!que.empty())que.pop();
		que.push(S);
		int now, to;
		
		while(!que.empty()){
			now = que.front();
			if(now == T)return true;
			que.pop();
			
			for(int i = head[now]; i; i = edge[i].ne){
				to = edge[i].to;
				
				if(deep[to] || edge[i].v <= 0)continue;
				deep[to] = deep[now] + 1;
				que.push(to);
				
			}
		}
		
		return deep[T];
	}
	
	int dfs(int now, int min_flow){
		if(now == T) return min_flow;
		
		int to, now_flow;
		for(int i = head[now]; i; i = edge[i].ne){
			to = edge[i].to;
			if(deep[to] != deep[now] + 1)continue;
			now_flow = dfs(to, min(min_flow, edge[i].v));
			if(!now_flow)continue;
			
			edge[i].v -= now_flow,
			edge[i].rv += now_flow;
			
			return now_flow;
		}
		return 0;
	}
	
	const inline void get_map(void){
		tot = 0;
		N = in();
		S = 1, T = N;
		int tmp;
		for(int i = 1; i <= N; ++i){
			for(int j = 1; j <= N; ++j){
				tmp = in();
				if(tmp)add_edge(i, j, tmp);
			}
		}
	}
	
	const inline void dinic(void){
		res = 0;
		while(bfs()){
			res += dfs(S, INF);
		}
	}
	
public:
	Max_flow(){}
	
	int work(){
		get_map();
		dinic();
		return res;
	}
}a;

void *Main(void){
#ifndef LOCAL
	freopen("maxflowa.in", "r", stdin);
	freopen("maxflowa.out", "w", stdout);
#endif
	printf("%d", a.work());
	return 0;
}
void *Main_(Main());
int main(){;}