记录编号	177898	评测结果	AAAAAAAAAA
题目名称	运输问题4	最终得分	100
用户昵称	真红之蝶	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2015-08-12 20:58:36	内存使用	1.46 MiB

/*在残量网络中有两类边：
1.剩余流量为零的边将其容量设为无穷，费用设为单位费用。
2.剩余流量不为零的边将其拆为两条边，一条容量设为剩余容量，费用设为0，另一条容量设为无穷，费用设为单位费用。*/
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,s,t,v[105],first[105],deep[105],dis[105],tat,tot=1,q[25000],head=0,tail=-1,ff,ww,pre[25000],ask;
struct bian
{
    int from,to,fare,next,flow;
}js[50000];
struct data
{
    int q,jvli;
    friend bool operator < (data a,data b)
    {
        return a.jvli>b.jvli;
    }
}cc,cd;
priority_queue<data>que;
int minc(int a,int b){return a<b?a:b;}
void add(int a,int b,int c,int d)
{
    js[++tot].from=a;
    js[tot].to=b;
    js[tot].flow=c;
    js[tot].fare=d;
    js[tot].next=first[a];
    first[a]=tot;
    js[++tot].from=b;
    js[tot].to=a;
    js[tot].flow=0;
    js[tot].fare=-d;
    js[tot].next=first[b];
    first[b]=tot;
}
/*int dfs(int x,int now_flow)
{
    if(x==n)
        return now_flow;
    int rest_flow=0;
    for(int i=first[x];i!=-1;i=js[i].next)
    {
        int u=js[i].to;
        if(js[i].flow>0&&deep[u]==deep[x]+1&&(rest_flow=dfs(u,minc(now_flow,js[i].flow))))
        {
            js[i].flow-=rest_flow;
            js[i^1].flow+=rest_flow;                                      
            return rest_flow;
        }
    }
    return 0;
}*/
/*bool bfs()
{
    head=0,tail=-1;
    q[++tail]=s;
    for(int i=1;i<=n;++i)
        deep[i]=-1;
    deep[s]=1;
    while(head<=tail)
    {
        int u=q[head++];
        for(int i=first[u];i!=-1;i=js[i].next)
        {
            int j=js[i].to;
            if(js[i].flow>0&&deep[j]==-1)
            {
                deep[j]=deep[u]+1;
                q[++tail]=j;
            }
        }
    }
    if(deep[t]>0)
        return 1;
    else
        return 0;
}*/
/*void dinic()
{
    int ans=0,ts=0;
    while(bfs())
        while(ts=dfs(1,0x7fffffff))
           ans+=ts;
    //printf("%d",ans);
}*/
bool spfa(int x)
{
    memset(dis,63,sizeof(dis));
    memset(v,0,sizeof(v));
    cc.q=x;
    cc.jvli=0;
    dis[x]=0;
    v[x]=1;
    que.push(cc);
    while(!que.empty())
    {
        cd=que.top();
        v[cd.q]=0;
        que.pop();
        for(int i=first[cd.q];i!=-1;i=js[i].next)
        {
            int u=js[i].to;
            if(js[i].flow>0&&dis[u]>dis[cd.q]+js[i].fare)
            {
                dis[u]=dis[cd.q]+js[i].fare;
                pre[u]=i;
                if(!v[u])
                {
                    v[u]=1;
                    cc.q=u;
                    cc.jvli=dis[u];
                    que.push(cc);
                }
            }
        }
    }
    if(dis[t]<100000000)
        return true;
    else
        return false;
}
void get_min()
{
    int minn=0x7fffffff;
    for(int i=pre[t];i;i=pre[js[i].from])
        minn=minc(minn,js[i].flow);  
    for(int i=pre[t];i;i=pre[js[i].from])
    {
        js[i].flow-=minn;
        js[i^1].flow+=minn;
        ask+=minn*js[i].fare;
    }
}
int main()
{
    freopen("maxflowd.in","r",stdin);
    freopen("maxflowd.out","w",stdout);
    memset(first,-1,sizeof(first));
    scanf("%d%d%d",&n,&s,&t);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            scanf("%d%d",&ff,&ww);
            if(ww&&ff)
               add(i,j,ff,ww); 
        }
    //dinic();
    while(spfa(s))
        get_min();
    printf("%d",ask);
    getchar();getchar();getchar();getchar();
    return 0;
}