记录编号	431155	评测结果	AAAAAAAAAA
题目名称	运输问题4	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-07-31 11:15:30	内存使用	0.00 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
#define inf 100000000
using namespace std;
int n,f[105][105],l[105][105],S,T;
int adj[10005],e=2,flag[10005],dis[10005],from[10005];
struct node
{
	int v,next,l,f;
} a[100000];
void add(int u,int v,int l,int f)
{
	a[e].v=v;a[e].next=adj[u];a[e].l=l;a[e].f=f;adj[u]=e++;
}
int read() {
	int s=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
	return s*f;
}
int bfs()
{
	for(int i=S+1;i<=T;i++)
	    dis[i]=inf;
	queue<int> q;
	q.push(S);
	flag[S]=1;
	while(!q.empty())
	{
		int x=q.front();q.pop();flag[x]=0;
		for(int i=adj[x];i;i=a[i].next)
		{
			int to=a[i].v;
			 if(a[i].l&&dis[to]>dis[x]+a[i].f)
			 {
			 	dis[to]=dis[x]+a[i].f;
			 	if(!flag[to])
			 	{
			 		flag[to]=1;
			 		q.push(to);
				}
				from[to]=i;
			 }
		}
	}
	if(dis[T]==inf)return 0;
	return dis[T];
}
int work()
{
	int p=T,f=inf;
	while(p!=S)
	{
		f=min(f,a[from[p]].l);
		p=a[from[p]^1].v;
	}
	p=T;
	while(p!=S)
	{
		a[from[p]].l-=f;
		a[from[p]^1].l+=f;
		p=a[from[p]^1].v;
	}
	return f;
}
int yjn()
{
	freopen("maxflowd.in","r",stdin);
	freopen("maxflowd.out","w",stdout);
	n=read();
	S=read();T=read();
	for(int i=1;i<=n;i++)
	   for(int j=1;j<=n;j++)
	   {
	   	     l[i][j]=read();
	   	     f[i][j]=read();
	   	     if(l[i][j])
	   	        add(i,j,l[i][j],f[i][j]),add(j,i,0,-f[i][j]);
	   }
	int ans=0,l;
	while(l=bfs())
	   ans+=work()*l;
	cout<<ans;   
}
int qty=yjn();
int main(){;}