记录编号	161161	评测结果	AAAAAAAAAA
题目名称	运输问题4	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2015-05-02 00:00:14	内存使用	0.32 MiB

#include<cstdio>
#include<iostream>
#include<deque>
#include<string.h>
using namespace std;
int N,st,ed,maxn=0xffffff,sw[110],last[110],e[110],ans=0;
class miku
{
	public:
	int fr,to,f,co;
	miku(){}
	miku(int x,int y,int c,int d)
	{
		fr=x,to=y,f=c,co=d;
	}
};
deque<miku> Q;
deque<int> G[110];
int check()
{
	for(int i=0;i<Q.size();i++)
		cout<<Q[i].fr<<" "<<Q[i].to<<" "<<Q[i].f<<" "<<Q[i].co<<endl;
	return 0;
}
void add(int x,int y,int f,int co)
{
	//cout<<x<<" "<<y<<" "<<f<<" "<<co<<" "<<Q.size()<<endl;
	G[x].push_back(Q.size());
	Q.push_back(miku(x,y,f,co));
}
int spfa()
{
	deque<int> q;
	int iq[110]={0};
	for(int i=1;i<=N;i++)
	{
		sw[i]=maxn;
		last[i]=0;
		e[i]=0;
	}
	sw[st]=0;iq[st]=1;q.push_back(st);e[st]=maxn;
	//check();
	while(!q.empty())
	{
		int x=q.front();q.pop_front();iq[x]=0;
		for(int j=0;j<G[x].size();j++)
		{
			miku w=Q[G[x][j]];
			//cout<<x<<" "<<w.to<<" "<<w.f<<" "<<w.co<<endl;
			if(w.f>0&&sw[x]+w.co<sw[w.to])
			{
				sw[w.to]=sw[x]+w.co;
				last[w.to]=G[x][j];
				e[w.to]=min(e[x],w.f);
				if(iq[w.to]==0)
				{
					iq[w.to]=1;
					q.push_back(w.to);
				}
			}
		}
	}
	if(sw[ed]==maxn) return 0;
	else
		return 1;
}
void push()
{
	int temp=ed,now=e[ed];
	ans+=sw[ed]*now;
	while(temp!=st)
	{
		int j=last[temp];
		Q[j].f-=now;
		Q[j^1].f+=now;
		temp=Q[j].fr;
	}
}
int main()
{
	freopen("maxflowd.in","r",stdin);
	freopen("maxflowd.out","w",stdout);
	
	scanf("%d%d%d",&N,&st,&ed);
	//printf("%d\n",1);
	for(int i=1;i<=N;i++)
	{
		
		for(int j=1;j<=N;j++)
		{
			int xx,yy;
			scanf("%d%d",&xx,&yy);
			if(xx>0)
			{
			add(i,j,xx,yy);
			add(j,i,0,-yy);
			}
		}
	}
	while(spfa()==1)
	{
		push();
	}
	printf("%d",ans);
	return 0;
}