记录编号	178396	评测结果	AAAAAAAAAA
题目名称	13.运输问题4	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2015-08-13 20:24:03	内存使用	0.33 MiB

# include <cstdio>
# include <cstring>
# include <iostream>
# include <algorithm>
# include <queue>

# define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

const int MAXN = 1100;

int ans;
int n,s,t,tot = 1;
int head[MAXN];
int dis[MAXN];
int path[MAXN];
bool vis[MAXN];

struct Edge{
	int u,v,w,next,flow;
}e[MAXN << 2];

struct Node{
	int id,val;
	friend bool operator < (Node a,Node b){
		return a.val > b.val;
	}
};

void add(int u,int v,int flow,int w){
	e[++tot].u = u;
	e[tot].v = v;
	e[tot].w = w;
	e[tot].flow = flow;
	e[tot].next = head[u];
	head[u] = tot;
}

void init(){
	int i,j,w,flow;
	scanf("%d%d%d",&n,&s,&t);
	for(i = 1;i <= n;++i)
		for(j = 1;j <= n;++j){
			scanf("%d%d",&flow,&w);
			if(flow && w) {
				add(i,j,flow,w);
				add(j,i,0,-w);
			}
		}	
}

bool spfa(int x){
	priority_queue <Node> q;
	memset(vis,0,sizeof(vis));
	memset(dis,63,sizeof(dis));
	Node ai,bi;
	ai.id = x;
	ai.val = 0;
	dis[x] = 0;
	vis[x] = 1;
	q.push(ai);
	while(!q.empty()){
		bi = q.top();
		q.pop();
		int u = bi.id;
		vis[u] = 0;
		for(int i = head[u];i;i = e[i].next){
			int v = e[i].v;
			if(e[i].flow && dis[v] > dis[u] + e[i].w){
				dis[v] = dis[u] + e[i].w;
				path[v] = i;
				if(!vis[v]){
					vis[v] = 1;
					ai.id = v;
					ai.val = dis[v];
					q.push(ai);
				}
			}
		}
	}
	if(dis[t] < 100000000) return 1;
	else return 0;
}

void work(){
	int res = 0x7fffffff;
	for(int i = path[t];i;i = path[e[i].u])	res = Min(res,e[i].flow);
	for(int i = path[t];i;i = path[e[i].u]){
		e[i].flow -= res;
		e[i ^ 1].flow += res;
		ans += res * e[i].w;
	}

}
int main(){
	freopen("maxflowd.in","r",stdin);
    freopen("maxflowd.out","w",stdout);
	init();
	while(spfa(s)) work();
	printf("%d",ans);
}