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

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
struct dd
{
	int zhong;
	int next;
	int cap;
	int cost;
}jie[10002];
int head[102],pre[102],tot,dis[102],n,s,t;
int a,b,ans;
bool v[102];
void add(int x,int y,int za,int zb)
{
	jie[tot].zhong=y;
	jie[tot].next=head[x];
	jie[tot].cap=za;
	jie[tot].cost=zb;
	head[x]=tot++;
}
bool spfa()
{
	queue<int>q;
	for(int i=1;i<=n;++i)
	  dis[i]=99999999;
	memset(v,0,sizeof(v));
	memset(pre,-1,sizeof(pre));
	q.push(s);
	v[s]=1;
	dis[s]=0;
	pre[s]=s;
	while(!q.empty())
	{
		int yu=q.front();
		q.pop();
		for(int i=head[yu];i!=-1;i=jie[i].next)
		{
			int lin=jie[i].zhong;
			if(dis[lin]>dis[yu]+jie[i].cost&&jie[i].cap>0)
			{
				dis[lin]=dis[yu]+jie[i].cost;
				pre[lin]=i;
				if(!v[lin])
				{
					v[lin]=1;
					q.push(lin);
				}
			}
		}
	}
	if(pre[t]!=-1) return true;
	return false;
}
void getflow()
{
	int d=99999999,p;
	for(int i=t;i!=s;i=jie[p^1].zhong) 
	{   p=pre[i];
		d=(d>jie[p].cap)?jie[p].cap:d;
	}
	for(int i=t;i!=s;i=jie[p^1].zhong)
	{   p=pre[i];
		jie[p].cap-=d;
		jie[p^1].cap+=d;
	}
	ans+=dis[t]*d;
}
int main()
{   freopen("maxflowd.in","r",stdin);
	freopen("maxflowd.out","w",stdout);
    memset(head,-1,sizeof(head));
	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,&b);
	 	if(a)
	 	{
	 		add(i,j,a,b);
	 		add(j,i,0,-b);
	 	}
	 }
	 while(spfa()) getflow();
	 printf("%d",ans);
}