记录编号	395248	评测结果	AAAAAAAAAA
题目名称	13.运输问题4	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2017-04-15 11:36:16	内存使用	0.36 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define inf 0x7fffffff
using namespace std;
int n,s,e,tmp;
bool pan[101];
int edgf[101][101],zq[101];
int cc[101];
vector<pair<int,int> > edg[101];
queue<int> q;
bool spfa()
{
	memset(cc,0x7f,sizeof(cc));
	memset(zq,0,sizeof(zq));
	pan[s]=1;q.push(s);cc[s]=0;
	while(!q.empty())
	{
		int now=q.front();
		pan[now]=0;q.pop();
		for(int i=0;i<edg[now].size();i++)
		{
			int md=edg[now][i].first,fy=edg[now][i].second;
			if(cc[now]+fy<cc[md]&&edgf[now][md]!=0)
			{
				cc[md]=cc[now]+fy;
				zq[md]=now;
				if(!pan[md])
				{
					q.push(md);
					pan[md]=1;
				}
			}
		}
	}
	if(zq[e]==0)return 0;
	return 1;
}
int dfs(int now,int flo)
{
	while(zq[now]!=0)
	{
		flo=min(flo,edgf[zq[now]][now]);
		now=zq[now];
	}
	now=e;
	while(zq[now]!=0)
	{
		edgf[zq[now]][now]-=flo;
		edgf[now][zq[now]]+=flo;
		now=zq[now];
	}
	return flo;
}
int main()
{
	freopen("maxflowd.in","r",stdin);
	freopen("maxflowd.out","w",stdout);
	scanf("%d%d%d",&n,&s,&e);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int f,m;
			scanf("%d%d",&f,&m);
			if(f==0)continue;
			edgf[i][j]+=f;
			edg[i].push_back(make_pair(j,m));
			edg[j].push_back(make_pair(i,-m));	
		}
	}
	int a=0;
	while(spfa())
	{
		tmp+=cc[e]*dfs(e,inf);
	}

	printf("%d",tmp);
	return 0;
}