记录编号	173712	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2015-07-29 17:03:11	内存使用	0.38 MiB

# include <cstdio>
# include <iostream>
# include <cstring>
# include <queue>

# define MAXN 101UL
# define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

const int INF = 0x3fffffff;

int n,tot = 1;
int maxflow;
int	a[MAXN][MAXN];
int head[MAXN];
int deep[MAXN];

struct Edge{
	int v,next,w;
}e[100*MAXN];

void add(int u,int v,int w){
	e[++tot].v = v;
	e[tot].w = w;
	e[tot].next = head[u];
	head[u] = tot;
}

bool bfs(){
	int i;
	memset(deep,0,sizeof(deep));
	queue <int> q;
	q.push(1);
	deep[1] = 1;
	while(!q.empty()){
		int u = q.front();
		q.pop();	
	    for(i = head[u];i;i = e[i].next){
	    	int v = e[i].v;
	    	if(e[i].w && !deep[v]){
	    		q.push(v);
	    		deep[v] = deep[u] + 1;
	    		if(v == n)	return 1;
			}
		}
	}
	return 0;
}

int dinic(int s,int f){
	if(s == n)	return f;
	int tmp = f;
	int k,i;
	for(i = head[s];i;i = e[i].next){
		int v = e[i].v;
		if(e[i].w && tmp && deep[v] == deep[s] + 1){
			k = dinic(v,Min(tmp,e[i].w));
			if(!k)	deep[v] = 0;
			e[i].w -= k;
			e[i ^ 1].w += k;
			tmp -= k;				
		}
	}
	return f-tmp;
}

int main(){
	freopen("maxflowa.in","r",stdin);
	freopen("maxflowa.out","w",stdout);
	int i,j;
	scanf("%d",&n);
	for(i = 1;i <= n; ++i)
		for(j = 1;j <= n; ++j){
			scanf("%d",&a[i][j]);
			if(a[i][j])	{
				add(i,j,a[i][j]);
				add(j,i,0);
			}
		}
	while(bfs())
		while(i = dinic(1,INF))
			maxflow += i;
	printf("%d",maxflow);			
}