CSU1506 Double Shortest Paths 最小花消最大流入门题

CSU1506 Double Shortest Paths 最小费用最大流入门题

题目链接：

csu1506

解题思路:

按照最小费用最大流的思想: 

每条边的容量表示可以经过的次数 ,每条边的费用表示经过这条边所需的费用

那么题目中的每条已给出的边 可以拆成两条容量为1的边：费用分别为di  di+ai

将源点与1连接   n与汇点连接  容量都为2  费用为0

这样跑出来的最小费用 就是答案所求

原理其实就是通过最大流中的反向边 纠正路线。

这样即使第一次走的不是全局最优的,但可以通过第二次走反向边纠正过来

最后得出全局最优解

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define INF 0x3f3f3f
#define maxn 1005
using namespace std;
struct node{
    int to,f,v,next;
}edge[maxn*10];
int head[maxn],ss;
int pre[maxn];
int n,s,t;
int ans;

void init()
{
    ss=0;
    ans=0;
    memset(head,-1,sizeof(head));
    memset(pre,0,sizeof(pre));
}

void addedge(int a,int b,int c,int w)
{
    edge[ss]=(node){b,c,w,head[a]};
    head[a]=ss++;
    edge[ss]=(node){a,0,-w,head[b]};
    head[b]=ss++;
}

int spfa()
{
    int vis[maxn]={0};
    int dis[maxn];
    memset(dis,INF,sizeof(dis));
    queue<int>q;
    int u,v;
    q.push(s);
    dis[s]=0;

    while(!q.empty())
    {
        u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].to;
            if(edge[i].f &&  dis[v]>dis[u]+edge[i].v)
            {
                dis[v]=dis[u]+edge[i].v;
                pre[v]=i;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(dis[t]<INF){
        ans+=dis[t];
        return 1;
    }
    return 0;
}

void MCMF()
{
    int d;
    while(spfa())       //能跑到汇点
    {
        for(int i=t;i!=s;i=edge[pre[i]^1].to)
        {
            edge[pre[i]].f--;;
            edge[pre[i]^1].f++;
        }
    }
}
int main()
{
//    freopen("in.txt","r",stdin);
    int m,a,b,c,d;
    int Case=1;
    while(~scanf("%d%d",&n,&m))
    {
        init();
        s=0,t=n+1;
        addedge(s,1,2,0);
        addedge(n,t,2,0);
        while(m--)
        {
            scanf("%d%d%d%d",&a,&b,&c,&d);
            addedge(a,b,1,c);
            addedge(a,b,1,c+d);    //拆为两条容量为1的边
        }
        MCMF();
        printf("Case %d: %d\n",Case++,ans);
    }
    return 0;
}