记录编号	173648	评测结果	AAAAAAAAAA
题目名称	运输问题4	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2015-07-29 15:47:00	内存使用	0.44 MiB

#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<cmath>
using namespace std;
const int maxn=102;
const int inf=0x7fffffff/3;
struct edge{
	int u,next,w,cost,v;
}G[maxn*10];
int dist[maxn];// 从起点s到点u的路径长为d
int vis[maxn];// 点u是否在队列中
int pre[maxn*100],h[maxn*100];
int tot=1,n,s,t,ans;
int path[maxn*100];

void add(int a,int b,int x,int y){
	G[++tot].v=b; G[tot].u=a;
	G[tot].w=x; G[tot].cost=y;
	G[tot].next=h[a]; h[a]=tot;
}

bool spfa(int s,int t){
    int u,v;
    queue<int>q;
    //memset(pre,-1,sizeof(pre));
    for(int i=0;i<=n+1;i++){
        pre[i]=0;
        vis[i]=0;
        dist[i]=inf;
    }
    vis[s]=1;
    dist[s]=0;
    q.push(s);
    while(!q.empty()){
        u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=h[u];i;i=G[i].next){
            if(G[i].w>0){
                v=G[i].v;
                if(dist[v]>dist[u]+G[i].cost){
                    dist[v]=dist[u]+G[i].cost;
                    pre[v]=u;
                    path[v]=i;
                    if(!vis[v]){
                        vis[v]=true;
                        q.push(v);
                    }
                }
            }
		}
    }
    return dist[t]!=inf/*&&pre[t]!=-1*/;
}

int smallest_cost_flow(){
    int ans=0,flow;
    int flow_sum=0;
    while(spfa(s,t)){
        flow=inf;
        //printf("%d ",dist[t]);
        for(int i=t;i!=s;i=pre[i]){
            if(G[path[i]].w<flow)
                flow=G[path[i]].w;
			//printf("%d ",i);
		}
		//printf("\n");
        for(int i=t;i!=s;i=pre[i]){
			
            G[path[i]].w-=flow;
            G[path[i]^1].w+=flow;
            //ans+=flow*G[path[i]].cost;
        }
		//printf("%d\n",flow);
		ans+=flow*dist[t];
        flow_sum+=flow;
        
    }
    return ans;
}

int main()
{
	freopen("maxflowd.in","r",stdin);
	freopen("maxflowd.out","w",stdout);
	scanf("%d%d%d",&n,&s,&t);
	int a,b;
	for (int i=1;i<=n;++i)
	   for (int j=1;j<=n;++j){
			scanf("%d%d",&a,&b);
			if (a!=0&&b!=0){
				add(i,j,a,b);
				add(j,i,0,-b);
			}
	   }
	printf("%d",smallest_cost_flow());
	//system("pause");
	return 0;
}