记录编号	246759	评测结果	AAAAAAAAAA
题目名称	运输问题4	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-04-07 09:48:09	内存使用	0.00 MiB

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
namespace cat{
	void read(int &x){
		x=0;char ch;
		while(ch=getchar(),ch<'!');
		while(x=10*x+ch-'0',ch=getchar(),ch>'!');
	}
	inline int cat_min(const int &a,const int& b){
		return a<b ? a:b;
	}
	int n,src,end;
	const int maxn = 100 ;
	const int INF = 0x7fffffff ;
	struct Edge{
		int from,to,next,flow,cost,cap;
	}G[(maxn<<1) + 10 ];
	int head[maxn+10],cnt=1;
	int d[maxn+10],p[maxn+10];
	bool inq[maxn+10];
	int a[maxn+10];
	void add(const int &x,const int &y,const int &cap,const int &cost){
		G[++cnt].to = y;
		G[cnt].from = x;
		G[cnt].cap = cap;
		G[cnt].cost= cost;
		G[cnt].next = head[x];
		head[x] = cnt;
	}
	int b[maxn+10],l,r;
	bool BellmanFord(int s,int t,int& flow,int& cost){
		memset(p,0,sizeof(p));
		for(int i=1;i<=n;i++) d[i] = INF ;
		memset(inq,0,sizeof(inq));
		d[s]=0;inq[s]=1;p[s]=0;a[s] = INF;
		l = r = 1;
		//queue<int> Q;Q.push(s);
		b[r] = s;
		int u;
		while(l<=r){
			u = b[l];l++;
			inq[u] = 0;
	//		printf("now doing %d\n",u);
	//		getchar();
			for(int i=head[u];i;i=G[i].next){
				if( G[i].cap > G[i].flow && d[G[i].to] > d[u] + G[i].cost ){
					d[G[i].to] = d[u] + G[i].cost;
					p[G[i].to] = i ;
					a[G[i].to] = cat_min(a[u],G[i].cap - G[i].flow);
					if( !inq[G[i].to] ) {
						b[++r] = G[i].to;
						inq[G[i].to] = 1;
					}
				}
			}
		}
		
		if(d[t] == INF) return false;
		flow += a[t];
		cost += d[t]*a[t];
		u = t;
		while(u != s){
			G[p[u]].flow += a[t];
			G[p[u]^1].flow -=a[t];
			u = G[p[u]].from;
		}
	//	printf("Debug point 1:\n");
	//	printf("Debug data d[t]:%d\na[t]:%d\n",d[t],a[t]);
	//	for(int i=1;i<=n;i++) printf("%d ",d[i]);
	//	printf("\n");
	//	printf("Then the ans is: %d\n",cost);
	//	getchar();
		return true;
	}
	int doo(){
		read(n);int cap,cost;
		read(src);read(end);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++){
				read(cap);read(cost);
				if( cap > 0 ){
					add(i,j,cap,cost);
					add(j,i,0,-cost);
				}
			}
		
		int flow=0;
		cost=0;
		while(BellmanFord(src,end,flow,cost));
	//	printf("ans is coming \n");
		printf("%d",cost);
	}
}
FILE *___=freopen("maxflowd.in","r",stdin);
FILE *_=freopen("maxflowd.out","w",stdout);
int ans=cat::doo();
int main(){;}