记录编号	99887	评测结果	AAAAAAAAAA
题目名称	运输问题4	最终得分	100
用户昵称	OI永别	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2014-05-01 20:42:25	内存使用	1.16 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define INF 0x7fffffff
#define N 111
#define M 51050
#define qm 111
int n,st,ed;
int mincost = 0;
vector <int> a[N],b[N];
struct arr{
	int ff,tt,ww,cost,next;
}c[M];
int r[N];
int dis[N],incf[N],lin[N];
int q[qm + 1];
bool v[N];
int tot = 1;
inline void add(int x,int y,int z,int cc){
	c[++tot].ff = x;c[tot].tt = y;c[tot].ww = z;c[tot].cost = cc;c[tot].next = r[x];r[x] = tot;
	c[++tot].ff = y;c[tot].tt = x;c[tot].ww = 0;c[tot].cost = -cc;c[tot].next = r[y];r[y] = tot;
}
bool spfa(){
	memset(dis,0x3f,sizeof(dis));
	memset(v,0,sizeof(v));
	dis[st] = 0;
	int h = 0, t = 0;
	q[++t] = st;
	incf[st] = INF;
	while (h != t){
		int x = q[h = (h % qm) + 1];
		v[x] = 0;
		for (int i = r[x]; i; i = c[i].next){
			int y = c[i].tt;
			if (c[i].ww > 0 && dis[y] > dis[x] + c[i].cost){
				dis[y] = dis[x] + c[i].cost;
				lin[y] = i;
				incf[y] = min(incf[x],c[i].ww);
				if (!v[y]){
					v[y] = 1;
					q[t = (t % qm) + 1] = y;
				}
			}
		}
	}
	if (dis[ed] == 0x3f3f3f3f) return 0;
	else return 1;
}

void EK(){
	int y,x = ed;
	while (lin[x]){
		y = x;
		x = c[lin[x]].ff;
		c[lin[y]].ww -= incf[ed];
		c[lin[y] ^ 1].ww += incf[ed];
	}
	mincost += dis[ed] * incf[ed];
	return;
}


int main(){
	freopen("maxflowd.in","r",stdin);
	freopen("maxflowd.out","w",stdout);
	scanf("%d%d%d",&n,&st,&ed);
	int x,y;
	for (int i = 1; i <= n; i ++){
		a[i].push_back(0),b[i].push_back(0);
		for (int j = 1; j <= n; j++){
			scanf("%d%d",&x,&y);
			a[i].push_back(x);b[i].push_back(y);
		}
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++){
			if (a[i].at(j)){
				add(i,j,a[i].at(j),b[i].at(j));
			}
		}
	while (spfa()){
		EK();
	}
	printf("%d\n",mincost);
	return 0;
}