UVa10806 - Dijkstra, Dijkstra.（費用流）

題目連結

簡介：

給出一個有n個節點，m條邊的帶權無向圖，找到起點S到終點T的最短往返路線不能重複走同一條邊

簡介：

這道題很像dijkstra求最短路和次短路

但是求解最短路次短路的時候，我們貫徹的是一種貪心思想，并且可以走重邊

如果隻是簡單地把最短路上的邊删除，再跑一邊最短路，是會出錯的

是以這道題就帶有一點dp的味道了

既像貪心，又像dp：網絡流

這道題的建圖很簡單，

因為我們要找出最短的兩條互不影響的路，是以我們用費用流解決

這樣就可以保證找到的一定是全脂和最小的路徑

但如果從S到T用多條路怎麼辦

很簡單，我們限制一下流量就好了

設超級源點SS，向S連邊，容量為2，費用為0

設超級彙點TT，T向其連邊，容量為2，費用為0

隻有增廣出來的總流量為2時，原問題才有解

//這裡寫代碼片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>

using namespace std;

const int INF=;
const int N=;
struct node{
    int x,y,v,c,nxt;
};
node way[N*N*];
int st[N],tot,n,m,s,t;
int pre[N],dis[N],ans;
bool in[N];

void add(int u,int w,int z,int cc)
{
    tot++;
    way[tot].x=u;way[tot].y=w;way[tot].v=z;way[tot].c=cc;way[tot].nxt=st[u];st[u]=tot;
    tot++;
    way[tot].x=w;way[tot].y=u;way[tot].v=;way[tot].c=-cc;way[tot].nxt=st[w];st[w]=tot;
}

int spfa(int s,int t)
{
    memset(pre,,sizeof(pre));
    memset(dis,,sizeof(dis));
    memset(in,,sizeof(in));

    queue<int> Q;
    Q.push(s);
    dis[s]=;  in[s]=;

    while (!Q.empty())
    {
        int now=Q.front(); Q.pop();
        in[now]=;
        for (int i=st[now];i!=-;i=way[i].nxt)
            if (way[i].v&&dis[way[i].y]>dis[now]+way[i].c)
            {
                dis[way[i].y]=dis[now]+way[i].c;
                pre[way[i].y]=i;
                if (!in[way[i].y])
                {
                    in[way[i].y]=;
                    Q.push(way[i].y);
                }
            }
    }
    return dis[t]<INF;
}

int doit(int s,int t)
{
    ans=;
    int flow=;
    while (spfa(s,t))
    {
        int sum=INF;
        for (int i=t;i!=s;i=way[pre[i]].x) 
            sum=min(sum,way[pre[i]].v);
        ans+=sum*dis[t]; flow+=sum;
        for (int i=t;i!=s;i=way[pre[i]].x)
            way[pre[i]].v-=sum,
            way[pre[i]^].v+=sum;
    }
    return flow;
}

int main()
{
    while (scanf("%d",&n)!=EOF&&n)
    {
        memset(st,-,sizeof(st));
        tot=-;

        scanf("%d",&m);
        for (int i=;i<=m;i++)
        {
            int u,w,z;
            scanf("%d%d%d",&u,&w,&z);
            add(u,w,,z);
            add(w,u,,z);
        }

        s=; t=n+;
        add(s,,,);
        add(n,t,,);

        int flow=doit(s,t);
        if (flow==) printf("%d\n",ans);
        else printf("Back to jail\n");
    }
    return ;
}