记录编号	177964	评测结果	AAAAAAAAAA
题目名称	13.运输问题4	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-08-12 21:48:50	内存使用	0.40 MiB

#include<cstdio>
#include<cstring>
#include<queue>

#define MIN(a,b) ((a)<(b)?(a):(b))

using namespace std;

int n,m,s,t,a[110][110],cost[110][110],dis[110],pre[110],ans;
bool flag[110];

bool SPFA()
{
	memset(dis,0x3f,sizeof(dis));
	memset(pre,0,sizeof(pre));
	queue<int> q;
	q.push(s);
	dis[s]=0;
	while(!q.empty()){
		int x=q.front();q.pop();flag[x]=0;
		for(int i=1;i<=n;i++){
			if(a[x][i]>0&&dis[i]>dis[x]+cost[x][i]){
				dis[i]=dis[x]+cost[x][i];
				pre[i]=x;
				if(!flag[i]){
					flag[i]=1;
					q.push(i);
				}
			}
		}
	}
	if(dis[t]<100000000)
		return 1;
	return 0;
}

void dfs()
{
	int tp=t,maxflow=0x3fffffff;
	while(pre[tp]){
		maxflow=MIN(maxflow,a[pre[tp]][tp]);
		tp=pre[tp];
	}
	tp=t;
	while(pre[tp]){
		a[pre[tp]][tp]-=maxflow;
		a[tp][pre[tp]]+=maxflow;
		tp=pre[tp];
	}
	ans+=maxflow*dis[t];
}

int main()
{
	freopen("maxflowd.in","r",stdin);
	freopen("maxflowd.out","w",stdout);
	scanf("%d%d%d",&n,&s,&t);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d%d",&a[i][j],&cost[i][j]);
			if(cost[i][j]>0){
				cost[j][i]=-cost[i][j];
			}
			else{
				cost[i][j]=-cost[j][i];
			}
		}
	}
	ans=0;
	while(SPFA()){
		dfs();
	}
	printf("%d",ans);
}