记录编号	367573	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2017-01-31 17:07:15	内存使用	0.57 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110;
struct edge{int to,cap,prev;}e[maxn*maxn<<1];
void addedge(int,int,int);
void AddEdge(int,int,int);
int Dinic();
void bfs();
int dfs(int,int);
int last[maxn],len=0,d[maxn],cur[maxn],q[maxn];
int n,s,t,x;
int main(){
	freopen("maxflowa.in","r",stdin);
	freopen("maxflowa.out","w",stdout);
	memset(last,-1,sizeof(last));
	scanf("%d",&n);
	s=1;t=n;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
		scanf("%d",&x);
		if(x)addedge(i,j,x);
	}
	printf("%d",Dinic());
	return 0;
}
void addedge(int x,int y,int z){
	AddEdge(x,y,z);
	AddEdge(y,x,0);
}
void AddEdge(int x,int y,int z){
	e[len].to=y;
	e[len].cap=z;
	e[len].prev=last[x];
	last[x]=len++;
}
int Dinic(){
	int flow=0;
	while(bfs(),d[t]!=-1){
		copy(last+1,last+n+1,cur+1);
		flow+=dfs(s,(~0u)>>1);
	}
	return flow;
}
void bfs(){
	int x,head=0,tail=0;
	fill(d+1,d+n+1,-1);
	q[tail++]=s;
	d[s]=0;
	while(head!=tail){
		x=q[head++];
		for(int i=last[x];i!=-1;i=e[i].prev)if(e[i].cap>0&&d[e[i].to]==-1){
			d[e[i].to]=d[x]+1;
			q[tail++]=e[i].to;
		}
	}
}
int dfs(int x,int a){
	if(x==t||!a)return a;
	int flow=0,f;
	for(int &i=cur[x];i!=-1;i=e[i].prev)if(e[i].cap>0&&d[e[i].to]==d[x]+1&&(f=dfs(e[i].to,min(a,e[i].cap)))){
		e[i].cap-=f;
		e[i^1].cap+=f;
		flow+=f;
		a-=f;
		if(!a)break;
	}
	return flow;
}