记录编号	431019	评测结果	AAAAAAAAAA
题目名称	运输问题4	最终得分	100
用户昵称	wangxh	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2017-07-31 07:27:33	内存使用	1.08 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
struct tree{
    int v,d,next,cost;
}l[50050];
int n,s,t,lian[105],e=-1,pre[105],path[105],dis[105],flow,zz;
void bian(int,int,int,int);
bool bfs();
void dinic();
int main()
{
    //freopen("in.txt","r",stdin);
    freopen("maxflowd.in","r",stdin);
    freopen("maxflowd.out","w",stdout);
    scanf("%d%d%d",&n,&s,&t);
    memset(lian,-1,sizeof(lian));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            bian(i,j,x,y);
            bian(j,i,0,-y);
        }
    dinic();
    printf("%d",zz);
    //while(1);
    return 0;
}
void bian(int x,int y,int a,int b)
{
    e++;
    l[e].v=y;
    l[e].d=a;
    l[e].cost=b;
    l[e].next=lian[x];
    lian[x]=e;
}
bool bfs()
{
    memset(pre,-1,sizeof(pre));
    memset(dis,30,sizeof(dis));
    dis[s]=0;
    queue<int> que;
    que.push(s);
    //cout<<s<<endl;
    while(que.empty()==0)
    {
        int x=que.front();
        que.pop();
        for(int i=lian[x];i!=-1;i=l[i].next)
        {
            int v=l[i].v;
            if(l[i].d>0&&dis[x]+l[i].cost<dis[v])
            {
                dis[v]=dis[x]+l[i].cost;
                pre[v]=x;
                path[v]=i;
                //cout<<dis[v]<<" "<<v<<" "<<dis[x]+l[i]<<endl;
                que.push(v);
            }
        }
    }
    if(pre[t]==-1)
        return false;
    return true;
}
void dinic()
{
    while(bfs()==1)
    {
        int f=0x7fffffff;
        for(int i=t;i!=s;i=pre[i])
            if(l[path[i]].d<f)
                f=l[path[i]].d;
        //cout<<f<<endl;
        flow+=f;
        zz+=dis[t]*f;
        for(int i=t;i!=s;i=pre[i])
        {
            l[path[i]].d-=f;
            l[path[i]^1].d+=f;
        }
    }
}