记录编号	236894	评测结果	AAAAAAAAAA
题目名称	运输问题4	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2016-03-15 19:47:01	内存使用	0.41 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;

struct way
{
	int f,v;
}w[110][110];
int n,s,t,i,j,ans,dist[110],z[110],r,f[110];
bool hash[110];
const int maxl=9999999;

bool dijsktra()
{
	int i,j,v,df;
	for (i=1;i<=n;i++) dist[i]=maxl;
	dist[s]=0;r=1;z[1]=s;hash[s]=true;
	while (r!=0){
		j=1;
		for (i=2;i<=r;i++) if (dist[z[j]]>dist[z[i]]) j=i;
		v=z[j];z[j]=z[r];r--;hash[v]=false;
		for (i=1;i<=n;i++)
		if (w[v][i].f>0&&dist[i]>dist[v]+w[v][i].v){
			dist[i]=dist[v]+w[v][i].v;f[i]=v;
			if (hash[i]==false){
				r++;z[r]=i;hash[i]=true;
			}
		}
	}
	if (dist[t]==maxl) return false;
	df=maxl;
	for (i=t;i!=s;i=f[i]) df=min(df,w[f[i]][i].f);
	for (i=t;i!=s;i=f[i]){
		w[f[i]][i].f-=df;w[i][f[i]].f+=df;
	}
	ans+=df*dist[t];
	//printf("%d\n",df);
	return true;
}

int main()
{
	freopen("maxflowd.in","r",stdin);
	freopen("maxflowd.out","w",stdout);
	scanf("%d%d%d",&n,&s,&t);
	for (i=1;i<=n;i++)
	for (j=1;j<=n;j++){
		scanf("%d%d",&w[i][j].f,&w[i][j].v);
		if (w[i][j].f!=0) w[j][i].v=-w[i][j].v;
	}
	while (dijsktra());
	printf("%d\n",ans);
	return 0;
}