记录编号	52861	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	馒头	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2013-02-17 19:53:07	内存使用	0.43 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define maxn 20000000
using namespace std;
int g[10000][3],a[200],d[200],vd[200],n,tot=1,ans,c;
void add(int u,int v,int w){
	g[++tot][1]=v;g[tot][2]=w;g[tot][3]=a[u];a[u]=tot;
	g[++tot][1]=u;g[tot][3]=a[v];a[v]=tot;
}
void init(){
	//sfreopen("test.in","r",stdin);
	freopen("maxflowa.in","r",stdin);
	freopen("maxflowa.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			scanf("%d",&c);
			if(c) add(i,j,c);
		}
}
int dfs(int k,int maxflow){
	if(k==n) return(maxflow);
	int mind=n-1,delta,s,now,flow=maxflow;
	for(int s=a[k];s;s=g[s][3]){
		now=g[s][1];
		if(g[s][2]){
			if(d[now]+1==d[k]){
				delta=dfs(now,min(g[s][2],flow));
				flow-=delta;
				g[s][2]-=delta;
				g[s^1][2]+=delta;
				if(d[1]>=n) return(maxflow-flow);
				if(!flow) break;
			}
		mind=min(mind,d[now]);
		}	
	}
	if(flow==maxflow){
		vd[d[k]]--;
		if(vd[d[k]]==0) d[1]=n;
		d[k]=mind+1;
		vd[d[k]]++;
	}
	return(maxflow-flow);
}
void sap(){
	memset(d,0,sizeof(d));
	memset(vd,0,sizeof(vd));
	vd[0]=n;
	while(d[1]<n) ans+=dfs(1,maxn);
	printf("%d",ans);
}
int main(){
	init();
	sap();
}