记录编号	99344	评测结果	AAAAAAAAAA
题目名称	运输问题4	最终得分	100
用户昵称	（ˇˍˇ） ～耶稣	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2014-04-27 11:23:05	内存使用	0.62 MiB

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

 const int u=210, M=15010;
 int ver[M],head[u],next[M],edge[M],w[M],d[u],q[M],last[u];
 int tot,n,ans,st,ed;
 bool v[M];
 
 inline int read()
 {
 	char ch;
 	while (!isdigit(ch = getchar()));
 	int ret=ch-48;
 	while (isdigit(ch = getchar()))
 	{
 		ret*=10;
 		ret+=ch-48;
 	}
 	return ret;
 }
 
 void add(int x, int y, int flow, int cost)
 {
 	ver[++tot]=y;
 	edge[tot]=flow;
 	w[tot]=cost;
 	next[tot]=head[x];
 	head[x]=tot;
 }
 
 bool spfa(void)
 {
 	memset(d,50,sizeof(d));
 	memset(v,0,sizeof(v));
 	int l,r,i,x,y;
 	l=r=1;
 	q[1]=st;
 	d[st]=0; v[st]=true;
 	while (l <= r)
 	{
 		x=q[l]; l++;
 		v[x]=false;
 		for (i=head[x]; i; i=next[i])
 		{
 			y=ver[i];
 			if (edge[i]>0 && d[y]>d[x]+w[i])
 			{
 				d[y]=d[x]+w[i];
 				last[y]=i;
 				if (!v[y])
 				{
 					v[y]=true; 
 					q[++r]=y;
 				}
 			}
 		}
 	}
 	if (d[ed] != d[ed+1]) return true;
 	else return false;
 }
 
 void updata(void)
 {
 	ans+=d[ed];
 	int temp,j;
 	temp=ed;
 	while (temp != st)
 	{
 		j=last[temp];
 		edge[j]-=1;
 		edge[j^1]+=1;
 		temp=ver[j^1];
 	}
 }
 
int main()
{
	freopen("maxflowd.in","r",stdin);
	freopen("maxflowd.out","w",stdout);
	
	n=read();
	st=read();
	ed=read();
	int i,j;
	tot=1;
	memset(head,0,sizeof(head));
	for (i=1; i<=n; i++)
	 for (j=1; j<=n; j++)
	 {
	 	int xx,yy;
	 	xx=read(); yy=read();
	 	if (xx>0)
	 	{
	 		add(i,j,xx,yy);
	 		add(j,i,0,-yy);
	 	}
	 }
	 ans=0;
	 memset(last,0,sizeof(last));
	 while (spfa())
	 {
	 	updata();
	 }
	 printf("%d",ans);
}