记录编号	430129	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-07-29 14:28:05	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define qq 1e9
int read() {
	int s=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0') {
		if(ch=='-') {
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		s=(s<<1)+(s<<3)+(ch^48);
		ch=getchar();
	}
	return s*f;
}
int n,r[105],tot,deep[105];
int head,tail,queue[105];
struct oo {
	int to,vv,next;
} c[10005];
void add(int x,int y,int z) {
	c[tot].to=y;
	c[tot].next=r[x];
	c[tot].vv=z;
	r[x]=tot++;
}
bool bfs(int s,int t) {
	memset(deep,0,sizeof(deep));
	head=tail=0;
	queue[++tail]=s;
	deep[s]=1;
	while(head<tail) {
		int opt=queue[++head];
		for(int i=r[opt]; ~i; i=c[i].next) {
			if(c[i].vv&&!deep[c[i].to]) {
				deep[c[i].to]=deep[opt]+1;
				queue[++tail]=c[i].to;
				if(c[i].to==t) {
					return 1;
				}
			}
		}
	}
	return 0;
}
int dfs(int opt,int fw) {
	if(opt==n) {
		return fw;
	}
	int tmp=fw,k;
	for(int i=r[opt]; ~i; i=c[i].next) {
		if(c[i].vv&&tmp&&deep[c[i].to]==deep[opt]+1) {
			k=dfs(c[i].to,min(c[i].vv,tmp));
			if(!k) {
				deep[c[i].to]=0;
				continue;
			}
			c[i].vv-=k;
			c[i^1].vv+=k;
			tmp-=k;
		}
	}
	return fw-tmp;
}
int dicnic(int s,int t){
	int ans=0;
	while(bfs(s,t)){
		ans+=dfs(s,qq);
	}
	return ans;
}
int Main(){
	freopen("maxflowa.in","r",stdin);
	freopen("maxflowa.out","w",stdout);
	n=read();
	memset(r,-1,sizeof(r));
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			int x=read();
			if(x) {
				add(i,j,x);
				add(j,i,0);
			}
		}
	}
	int ans=dicnic(1,n);
	printf("%d\n",ans);
	return 0;
}
int hehe=Main();
int main() {
	;
}