记录编号	360879	评测结果	AAAAAAAAAA
题目名称	运输问题4	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2017-01-02 06:34:17	内存使用	0.68 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=110,maxe=maxn*maxn;
struct edge{int to,cap,cost,prev;}e[maxe<<1];
void addedge(int,int,int,int);
void AddEdge(int,int,int,int);
int MCMF();
void SPFA();
int last[maxn],len=0,dis[maxn],p[maxn];
bool inq[maxn];
int n,cap,cost,s,t;
int main(){
	freopen("maxflowd.in","r",stdin);
	freopen("maxflowd.out","w",stdout);
	memset(last,-1,sizeof(last));
	scanf("%d%d%d",&n,&s,&t);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
		scanf("%d%d",&cap,&cost);
		if(cap)addedge(i,j,cap,cost);
	}
	printf("%d",MCMF());
	return 0;
}
void addedge(int x,int y,int z,int w){
	AddEdge(x,y,z,w);
	AddEdge(y,x,0,-w);
}
void AddEdge(int x,int y,int z,int w){
	e[len].to=y;
	e[len].cap=z;
	e[len].cost=w;
	e[len].prev=last[x];
	last[x]=len++;
}
int MCMF(){
	int cost=0;
	while(SPFA(),dis[t]<0x3f3f3f3f){
		int x,delta=(~0u)>>1;
		for(x=t;x!=s;x=e[p[x]^1].to)delta=min(delta,e[p[x]].cap);
		cost+=dis[t]*delta;
		for(x=t;x!=s;x=e[p[x]^1].to){
			e[p[x]].cap-=delta;
			e[p[x]^1].cap+=delta;
		}
	}
	return cost;
}
void SPFA(){
	queue<int>q;
	memset(dis,63,sizeof(dis));
	memset(inq,0,sizeof(inq));
	q.push(s);
	dis[s]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		inq[x]=false;
		for(int i=last[x];i!=-1;i=e[i].prev)if(e[i].cap>0&&dis[e[i].to]>dis[x]+e[i].cost){
			dis[e[i].to]=dis[x]+e[i].cost;
			p[e[i].to]=i;
			if(!inq[e[i].to]){
				inq[e[i].to]=true;
				q.push(e[i].to);
			}
		}
	}
}