记录编号	537554	评测结果	AAAAAAAAAA
题目名称	11.运输问题1	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2019-07-14 09:21:26	内存使用	48.69 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
const int maxn=1010;
struct Edge{
	int next,to,flow,cap;
}e[maxn*maxn*2];
int len,head[maxn],cur[maxn];
void Insert(int x,int y,int z){ 
	len++;e[len].to=y;e[len].next=head[x];e[len].cap=z;head[x]=len;
}
void Add_edge(int x,int y,int flow){
	Insert(x,y,flow);Insert(y,x,0);
}
int S,T,ansflow,n;
int dis[maxn],nodis;
int q[maxn*maxn],Head,Tail;
bool Bfs(){
	Head=Tail=0;q[Tail++]=S;
	memset(dis,-1,sizeof(dis));dis[S]=0;
	nodis=dis[T];
	while(Head^Tail){
		int k=q[Head++];
		for(int i=head[k];i;i=e[i].next){
			int j=e[i].to;
			if(dis[j]<0 && e[i].cap>e[i].flow){
				dis[j]=dis[k]+1;
				q[Tail++]=j; 
			}
		}
	}
	return dis[T]!=nodis;
}
#define ex(x) ( (x&1) ? (x+1) : (x-1) )
int Dfs(int x,int flow){
	if(x==T || flow==0) return flow;
	int tot=0;
	for(int &i=cur[x];i;i=e[i].next){
		int j=e[i].to;
		if(e[i].cap>e[i].flow && dis[j]==dis[x]+1){
			int dd=Dfs(j,min(flow,e[i].cap-e[i].flow));
			e[i].flow+=dd;e[ex(i)].flow-=dd;
			tot+=dd;flow-=dd;
			if(!flow) break;
		}
	}
	return tot;
}
void Maxflow(){
	ansflow=0;
	while(Bfs()){
		memcpy(cur,head,sizeof(head));
		ansflow+=Dfs(S,Inf);
	}
}
void Init();
int main(){
	freopen("maxflowa.in","r",stdin);
	freopen("maxflowa.out","w",stdout);
	Init();
	return 0;
}
void Init(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int x;scanf("%d",&x);
			if(x) Add_edge(i,j,x);	
		}
	} 
	S=1;T=n;
	Maxflow();
	printf("%d\n",ansflow);
}