UVA10806 Dijkstra, Dijkstra. （无向图最小费用最大流/最短路）

Dijkstra, Dijkstra.

You are a political prisoner in jail. Things are looking grim, but fortunately, your jailmate has come up with an escape plan. He has found a way for both of you to get out of the cell and run through the city to the train station, where you will leave the country. Your friend will escape first and run along the streets of the city to the train station. He will then call you from there on your cellphone (which somebody smuggled in to you inside a cake), and you will start to run to the same train station. When you meet your friend there, you will both board a train and be on your way to freedom.
Your friend will be running along the streets during the day, wearing his jail clothes, so people will notice. This is why you can not follow any of the same streets that your friend follows - the authorities may be waiting for you there. You have to pick a completely different path (although you may run across the same intersections as your friend).
What is the earliest time at which you and your friend can board a train?

Problem, in short

Given a weighed, undirected graph, find the shortest path from S to T and back without using the same edge twice.

Input

The input will contain several test cases. Each test case will begin with an integer n (2 ≤ n ≤ 100) — the number of nodes (intersections). The jail is at node number 1, and the train station is at node number n. The next line will contain an integer m — the number of streets. The next m lines will describe the m streets. Each line will contain 3 integers — the two nodes connected by the street and the time it takes to run the length of the street (in seconds). No street will be longer than 1000 or shorter than 1. Each street will connect two different nodes. No pair of nodes will be directly connected by more than one street. The last test case will be followed by a line containing zero.

Output

For each test case, output a single integer on a line by itself — the number of seconds you and your friend need between the time he leaves the jail cell and the time both of you board the train. (Assume that you do not need to wait for the train — they leave every second.) If there is no solution, print ‘Back to jail’.

Sample Input

Sample Output

Back to jail
80
Back to jail

链接

https://cn.vjudge.net/problem/UVA-10806

题意

给出一个带有n(n<=100)个节点的带权无向图，找到从起点S到终点T的最短往返路径，不能重复走过同一条边。输入图中不含重边。

题解

转化为无向图的最小费用最大流。建立一个超级源与超级汇，因为要求往返最短路径，所以超级源与起点连一条容量为2费用为0的边，终点与超级汇连一条容量为2费用为0的边。原图的边转化为两条有向边，其中流量为1费用为边权。然后跑一遍最小费用最大流，如果最大流为2那么输出最小费用，否则输出Back to jail。

为什么这样做一定是正确的呢？首先因为每条边只能走一次，所以需要将容量设置为1，又因为需要走往返路径，所以源点/汇点与起点/终点之间的容量设置为2。但是由于是无向图，转化为两条有向边后，原图的每两个点之间就有了四条边（每条有向边有对应的反向边），我的疑问是为什么求解最大流的时候能保证只会经过一条有向边，kuangbin聚聚的回答是：

bin神，昨天问的那个题还是没太明白，就是无向图最小费用最大流转化为两条有向边的时候不会走两条，它的相互抵消指的是什么呢？两条有向边的容量都为正呀。
麻烦bin神有时间的时候解答下，谢啦
是的，容量都为正，费用流可以理解成一条河流，两个点之间只会有单向的存在。如果他们费用都是正的，那么应该互相抵消

还是不太理解，感觉是由于最小费用的限制，导致它不会走两条反向边。网上还有使用两边最短路解决这个问题的，tql.

用两次spfa，１到ｎ走两次．但是第一次用完，要做一下处理，把走过的路变成inf不能再走，而反向边变为相反数．这与最大流更新反向边作用一样，是为了修正之前的最大值．——传送门

网上还有一种解释：

最终我是用最小费用最大流来解决的，通过这个题目，我对最大流有了更深刻的理解，明白了残量图的更大的作用，为什么当时E-K算法里面，找到增广路后需要对正向流进行扩展，同时又对反向流减少，这其实就是对应了现实的流的概念，我递增正向，但是流是守恒的，我可以通过反向把流又送回来，因此用这个方法，使得最大流不会放过任何一个能走通的路径，在E-K算法里，其实流经过了多次往返，只有确定无法走通，才会放弃。。。同时在建图的时候，因为是无向图，所以每条边，都要建立一个相应的负费用边。。。这样的话每个端点实际上连了两条边，一个是自己的正费用边，一个是对面端点的负费用边，我一开始会觉得这样在最短路过程中会不会发生混乱，即这个点往下走，到底是走的自己本身的正费用边，还是负费用边，后来不管费用如何，最短路最终会选择最优的那条，因此不会有问题。

代码

Status	Accepted
Length	2754

最小费用最大流

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 110; // 点数
const int maxm = 10010; // 边数
const int inf = 0x3f3f3f3f;

struct Edge
{
    int to, next, cap, flow, cost;
}edge[maxm<<2];

int head[maxn], pre[maxn], dis[maxn];
int n, m, tot;
bool vis[maxn];

void init()
{
    memset(head, -1, sizeof(head));
    tot = 0;
}

void addedge(int u, int v, int cap, int cost) // 链式前向星存图
{
    edge[tot].to = v;
    edge[tot].cap = cap;
    edge[tot].cost = cost;
    edge[tot].flow = 0;
    edge[tot].next = head[u];
    head[u] = tot++;
    edge[tot].to = u;
    edge[tot].cap = 0;
    edge[tot].cost = -cost;
    edge[tot].flow = 0;
    edge[tot].next = head[v];
    head[v] = tot++;
}

bool spfa(int s, int t) // spfa寻找最小费用增广路
{
    queue <int> Q;
    for (int i = 0; i <= n + 1; ++i)
    {
        dis[i] = inf;
        vis[i] = false;
        pre[i] = -1;
    }
    dis[s] = 0;
    vis[s] = true;
    Q.push(s);
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        vis[u] = false;
        for (int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].to;
            if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost)
            {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if (!vis[v])
                {
                    vis[v] = true;
                    Q.push(v);
                }
            }
        }
    }
    if (pre[t] == -1)
        return false;
    return true;
}

int minCostMaxflow(int s, int t, int &mincost) // 计算费用
{
    int maxflow = 0;
    mincost = 0;
    while (spfa(s, t))
    {
        int Min = inf;
        for (int i = pre[t]; i != -1; i = pre[edge[i^1].to]) // 每次增加的流量
            Min = min(Min, edge[i].cap - edge[i].flow);
        for (int i = pre[t]; i != -1; i = pre[edge[i^1].to])
        {
            edge[i].flow += Min;
            edge[i^1].flow -= Min;
            mincost += edge[i].cost * Min;
        }
        maxflow += Min;
    }
    return maxflow;
}

int main()
{
    int u, v, cost, cap, s, t;
    while (scanf("%d", &n) != EOF)
    {
        if (n == 0)
            break;
        scanf("%d", &m);
        init();
        s = 0, t = n + 1, cap = 1;
        for (int i = 1; i <= m; ++i) // 无向边转化为两条有向边
        {
            scanf("%d%d%d", &u, &v, &cost);
            addedge(u, v, cap, cost);
            addedge(v, u, cap, cost);
        }
        addedge(s, 1, 2, 0); // 超级源和起点，容量为2，费用为0
        addedge(n, t, 2, 0); // 终点和超级汇，容量为2，费用为0
        int maxflow, mincost = 0;
        maxflow = minCostMaxflow(s, t, mincost);
        if (maxflow != 2) // 最大流不为2，失败
            printf("Back to jail\n");
        else
            printf("%d\n", mincost);
    }
    return 0;
}

两遍spfa

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f;
int g[N][N];
int d[N];
int p[N];
int vis[N];
int n, m;
int s, t;
int spfa(int s, int t) {
    queue<int> q;
    memset(vis , 0 ,sizeof(vis));
    for(int i = 1; i <= n; i++) 
        d[i] = (i == s) ? 0 : INF;
    q.push(s);
    while(!q.empty()){
        int u = q.front(); q.pop();
        vis[u] = 0;
        for(int v = 1; v <= n; v++) if(g[u][v]){
            if(d[v] > d[u] + g[u][v]) {
                d[v] = d[u] + g[u][v];
                p[v] = u;
                if(!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return d[t];
}
void change(int u) {
    if(p[u] == -1)
        return ;
    g[u][p[u]] = -g[u][p[u]];
    g[p[u]][u] = INF;
    change(p[u]);
}
int main(){
    while(scanf("%d",&n) && n) {
        memset(g, INF, sizeof(g));
        memset(p, -1, sizeof(p));
        scanf("%d", &m);
        while(m--) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g[a][b] = g[b][a] = c;
        }
        int ans = spfa(1, n);
        change(n);
        ans += spfa(1, n);
        if(ans < INF)
            printf("%d\n", ans);
        else
            printf("Back to jail\n");
    }
    return 0;
}

The end.
2018-08-21 星期二