记录编号	321855	评测结果	AAAAAAAAAA
题目名称	13.运输问题4	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-10-14 07:33:33	内存使用	0.00 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF ((~(1<<31))>>1)
using namespace std;
const int maxn=1010;
struct edge{int to,cap,cost,prev;}e[maxn*maxn],ee[maxn*maxn];
void addedge(int,int,int,int);
void insert(int,int,int,int);
int mincostmaxflow();
int Dinic();
void bfs();
int dfs(int,int);
void SPFA();
int n,len=0,last[maxn],d[maxn],now[maxn],p[maxn],q[maxn<<4],head,tail,s,t,z,w;
bool inq[maxn];
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("maxflowd.in","r",stdin);
	freopen("maxflowd.out","w",stdout);
#endif
	scanf("%d%d%d",&n,&s,&t);
	fill_n(last+1,n,-1);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
		scanf("%d%d",&z,&w);
		if(z)addedge(i,j,z,w);
	}
	printf("%d",mincostmaxflow());
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
int AntiLeaf=MAIN();
int main(){;}
void addedge(int x,int y,int z,int w){
	insert(x,y,z,w);
	insert(y,x,0,-w);
}
void insert(int x,int y,int z,int w){
	e[len].to=y;
	e[len].cap=z;
	e[len].cost=w;
	e[len].prev=last[x];
	last[x]=len++;
}
int mincostmaxflow(){
	copy(e,e+len,ee);
	int ans=0,flow=Dinic(),delta,x;
	copy(ee,ee+len,e);
	while(flow){
		SPFA();
		delta=~(1<<31);
		for(x=t;x!=s;x=e[p[x]^1].to)delta=min(delta,e[p[x]].cap);
		delta=min(delta,flow);
		flow-=delta;
		for(x=t;x!=s;x=e[p[x]^1].to){
			ans+=e[p[x]].cost*delta;
			e[p[x]].cap-=delta;
			e[p[x]^1].cap+=delta;
		}
	}
	return ans;
}
int Dinic(){
	int ans=0;
	for(;;){
		bfs();
		if(d[t]==INF)break;
		fill_n(now+1,n,0);
		ans+=dfs(s,INF);
	}
	return ans;
}
void bfs(){
	int x;
	fill_n(d+1,n,INF);
	d[s]=0;
	head=tail=0;
	q[tail++]=s;
	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]==INF){
			d[e[i].to]=d[x]+1;
			q[tail++]=e[i].to;
		}
	}
}
int dfs(int x,int delta){
	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(e[i].cap>0&&d[e[i].to]==d[x]+1){
		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;
		flow+=f;
		delta-=f;
		if(!delta)break;
	}
	return flow;
}
void SPFA(){
	int x;
	fill_n(d+1,n,INF);
	fill_n(inq+1,n,false);
	d[s]=0;
	head=tail=0;
	q[tail++]=s;
	while(head!=tail){
		x=q[head++];
		inq[x]=false;
		for(int i=last[x];i!=-1;i=e[i].prev)if(e[i].cap>0&&d[e[i].to]>d[x]+e[i].cost){
			d[e[i].to]=d[x]+e[i].cost;
			p[e[i].to]=i;
			if(!inq[e[i].to]){
				inq[e[i].to]=true;
				q[tail++]=e[i].to;
			}
		}
	}
}