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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x7fffffff
int n,m,x,y,s,t,sum,num;
int adj[101];
struct flow{
	int t,w,v,next;
}k[10001];
int read(){
	int sum=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') {sum=sum*10+ch-'0';ch=getchar();}
	return sum;	
}
void init(int s,int t,int w,int v){
	k[num].t=t;k[num].w=w;k[num].v=v;
	k[num].next=adj[s];adj[s]=num++;
	k[num].t=s;k[num].w=0;k[num].v=-v;
	k[num].next=adj[t];adj[t]=num++;
}
int dis[101],path[101],pre[101];
bool bfs(){
	memset(dis,0x3f,sizeof(dis));
	memset(pre,-1,sizeof(pre));
	std::queue<int>q;
	q.push(s);dis[s]=0;
	while(!q.empty()){
		int o=q.front();q.pop();
		for(int i=adj[o];i!=-1;i=k[i].next){
			if(!k[i].w||dis[k[i].t]<=dis[o]+k[i].v) continue;
			dis[k[i].t]=dis[o]+k[i].v;
			pre[k[i].t]=o;path[k[i].t]=i;
			q.push(k[i].t);
		}
	}
	if(pre[t]==-1) return false;
	return true;
}
void Dinic(){
	int f;
	while(bfs()){
		f=inf;
		for(int i=t;i!=s;i=pre[i])
			if(f>k[path[i]].w)
				f=k[path[i]].w;
		sum+=dis[t]*f;
		for(int i=t;i!=s;i=pre[i])
			k[path[i]].w-=f,k[path[i]^1].w+=f;
	}
}
int main(){
	freopen("maxflowd.in","r",stdin);
	freopen("maxflowd.out","w",stdout);
	memset(adj,-1,sizeof(adj));
	n=read();s=read();t=read();
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			x=read();y=read();
			if(x||y) init(i,j,x,y);
		}
	Dinic();
	printf("%d\n",sum);
	 //while(1);
	return 0;
}