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

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
namespace cat{
	void read(int &x){
		x=0;char ch;
		while(ch=getchar(),ch<'!');
		while(x=10*x+ch-'0',ch=getchar(),ch>'!');
	}
	inline int cat_min(const int a,const int b){
		return a<b ? a:b;
	}
	int n;
	const int maxn = 100 ;
	const int INF = 0x7fffffff ;
	int w[maxn+10][maxn+10];
	int dist[maxn+10];
	int b[maxn+10],l,r;
	bool BFS(){
		l = r = 1;
		memset(dist,-1,sizeof(dist));
		dist[1] = 1;
		b[r]=1;
		int t;
		while(l<=r){
			t = b[l];l++;
			for(int i=1;i<=n;i++){
				if( w[t][i] && dist[i]<0 ){
					dist[i] = dist[t] +1;
					b[++r]=i;
				}
			}
		}
		if(dist[n] < 0) return false;
		return true;
	}
	int DFS(int s,int flow){
		if( s == n ) return flow;
		int t;
		for(int i=1;i<=n;i++){
			if( dist[i] == dist[s] + 1 ){
				if( t = DFS(i,cat_min(flow,w[s][i]))) {
					w[s][i] -= t ;
					w[i][s] += t ;
					return t ;
				}
			}
		}
		return 0;
	}
	int doo(){
		read(n);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				read(w[i][j]);
		int ans=0,flow;
		while(BFS()){
			while( flow = DFS(1,INF) ) ans+=flow;
		}
		printf("%d",ans);
	}
}
FILE *___=freopen("maxflowa.in","r",stdin);
FILE *_=freopen("maxflowa.out","w",stdout);
int ans = cat::doo();
int main(){;}