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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110;
struct edge{
	int to,prev,cap;
}e[maxn*maxn<<1];
void insert(int,int,int);
int Dinic();
void bfs(int);
int dfs(int,int);
int n,last[maxn],d[maxn],len=0;
int q[maxn],head,tail,now[maxn],s,t,tmp;
bool vis[maxn];
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("maxflowa.in","r",stdin);
	freopen("maxflowa.out","w",stdout);
#endif
	memset(last,-1,sizeof(last));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
		scanf("%d",&tmp);
		if(!tmp)continue;
		insert(i,j,tmp);
		insert(j,i,0);
	}
	//scanf("%d",&tmp);while(tmp--){int x,y,z;scanf("%d%d%d",&x,&y,&z);insert(x,y,z);insert(y,x,0);}
	s=1;t=n;
	printf("%d",Dinic());
#ifndef MINE
	printf("\n--------------------DONE--------------------\n");
	for(;;);
#endif
	return 0;
}
int hzoier=MAIN();
int main(){;}
void insert(int x,int y,int z){
	e[len].to=y;
	e[len].prev=last[x];
	e[len].cap=z;
	last[x]=len++;
}
int Dinic(){
	int ans=0;
	for(;;){
		bfs(s);
		if(!vis[t])break;
		memset(now,0,sizeof(now));
		ans+=dfs(s,~(1<<31));
	}
	return ans;
}
void bfs(int x){
	memset(vis,0,sizeof(vis));
	d[x]=0;
	vis[x]=true;
	head=tail=0;
	q[tail++]=x;
	while(head!=tail){
		x=q[head++];
		for(int i=last[x];i!=-1;i=e[i].prev){
			if(e[i].cap<=0||vis[e[i].to])continue;
			vis[e[i].to]=true;
			d[e[i].to]=d[x]+1;
			q[tail++]=e[i].to;
		}
	}
}
int dfs(int x,int delta){
	//printf("dfs(%d) delta=%d d=%d\n",x,delta,d[x]);
	if(x==t||!delta)return delta;
	int flow=0,f;
	for(int i=(now[x]?e[now[x]].prev:last[x]);i!=-1;i=e[i].prev){
		if(d[e[i].to]!=d[x]+1)continue;
		now[x]=i;
		f=dfs(e[i].to,min(delta,e[i].cap));
		if(!f)continue;
		e[i].cap-=f;
		e[i^1].cap+=f;
		delta-=f;
		flow+=f;
		if(!delta)break;
	}
	return flow;
}
/*
6 7
1 2 10
1 3 10
2 4 4
2 5 8
3 5 9
4 6 10
5 6 10
Answer:
14
*/