记录编号	430208	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2017-07-29 15:29:34	内存使用	1.08 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
#define LL long long
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 40000
const int inf=0x7fffffff;
struct haha{
	int next,to,w;
}edge[N];
int head[N],cnt;
int n;
void add(int u,int v,int w){
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
int dep[N],ans;
bool bfs(){
	memset(dep,0,sizeof(dep));
	queue<int> q;
	q.push(1);
	dep[1]=1;
	while(!q.empty()){
		int now=q.front();q.pop();
		for(int i=head[now];i!=-1;i=edge[i].next){
			int to=edge[i].to,w=edge[i].w;
			if(w&&(!dep[to])){
				dep[to]=dep[now]+1;
				q.push(to);
				if(to==n){
					return 1;
				}
			}
		}
	}
	return 0;
}
int dfs(int now,int f){
	if(now==n){
		return f;
	}
	int tmp=f;
	for(int i=head[now];i!=-1;i=edge[i].next){
		int to=edge[i].to,w=edge[i].w;
		if(w&&tmp&&dep[to]==dep[now]+1){
			int k=dfs(to,min(w,tmp));
			if(!k){
				dep[to]=0;
				continue;
			}
			edge[i].w-=k;
			edge[i^1].w+=k;
			tmp-=k;
		}
	}
	return f-tmp;
}
/*int hea,tail,que[N];
bool bfs() {
	memset(dep,0,sizeof(dep));
	hea=tail=0;
	que[++tail]=1;
	dep[1]=1;
	while(hea<tail) {
		int opt=que[++hea];
		for(int i=head[opt]; i; i=edge[i].next) {
			if(edge[i].w&&!dep[edge[i].to]) {
				dep[edge[i].to]=dep[opt]+1;
				que[++tail]=edge[i].to;
				if(edge[i].to==n) {
					return 1;
				}
			}
		}
	}
	return 0;
}
int dfs(int opt,int fw) {
	if(opt==n) {
		return fw;
	}
	int tmp=fw,k;
	for(int i=head[opt]; i; i=edge[i].next) {
		if(edge[i].w&&tmp&&dep[edge[i].to]==dep[opt]+1) {
			k=dfs(edge[i].to,min(edge[i].w,tmp));
			if(!k) {
				dep[edge[i].to]=0;
				continue;
			}
			edge[i].w-=k;
			edge[i^1].w+=k;
			tmp-=k;
		}
	}
	return fw-tmp;
}*/
int main(){
	freopen("maxflowa.in","r",stdin);
	freopen("maxflowa.out","w",stdout);
	scanf("%d",&n);
	memset(head,-1,sizeof(head));
	pos(i,1,n){
		pos(j,1,n){
			int x;
			scanf("%d",&x);
			if(x){
				add(i,j,x);
				add(j,i,0);
			}
		}
	}
	while(bfs()){
		ans+=dfs(1,inf);
	}
	cout<<ans;
	return 0;
}