题目描述

你是一名政治犯，被关在监狱中。你的狱友设计了一个逃跑计划：他先越狱，沿着城市街道跑到火车站，然后打电话给你，你再从监狱出发，沿着与他完全不同的路径（不能走他走过的任何一条街道，但可以经过相同的路口）跑到火车站会合，然后一起上火车离开。

给定一个无向加权图，节点 $1$ 是监狱，节点 $n$ 是火车站。你需要找到两条从节点 $1$ 到节点 $n$ 的边不相交的路径，使得这两条路径的总长度最小。如果无法找到两条这样的路径，则输出 Back to jail。

输入格式

输入包含多个测试用例。每个测试用例以整数 $n$ （$2\le n\le 100$）开始，表示节点数。接下来一行是整数 $m$ ，表示街道数。随后 $m$ 行每行包含三个整数 $u,v,t$ ，表示连接节点 $u$ 和 $v$ 的街道长度为 $t$ （$1\le t\le 1000$ ）。输入以一行包含 $0$ 结束。

输出格式

对于每个测试用例，输出一个整数表示两人从离开监狱到都登上火车所需的最短总时间（秒）。如果无法完成，输出 Back to jail。

题目分析与建模

本题的核心是：在无向图中寻找两条从源点 $1$ 到汇点 $n$ 的边不相交路径，使得它们的总长度最小。

这实际上是一个最小费用最大流问题：

• 节点：图中的每个路口。
• 边：将原图的每条无向边转化为两条方向相反的有向边，每条有向边的容量设为 $1$ ，费用设为该边的长度。
• 源点和汇点：添加一个超级源点 $0$ ，从 $0$ 向节点 $1$ 连接一条容量为 $2$ 、费用为 $0$ 的边，表示需要两条从 $1$ 到 $n$ 的流。汇点就是节点 $n$ 。

这样，问题转化为：在构建的流网络中寻找从 $0$ 到 $n$ 的流量为 $2$ 的最小费用流。如果最大流量小于 $2$ ，则无解。

为什么可以这样建模？

1. 每条边的容量为 $1$ ，确保每条边最多被使用一次，满足“边不相交”的条件。
2. 由于原图是无向图，我们将其拆分为两条有向边，分别表示两个方向的通行。
3. 从超级源点 $0$ 到节点 $1$ 的容量 $2$ 表示需要两条路径。
4. 最小费用流算法会寻找总长度最小的两条路径。

算法设计

使用 $\text{SPFA（Shortest Path Faster Algorithm）}$ 实现的 最小费用最大流（$\text{MCMF}$） 算法：

1. 构建网络：根据输入构建带容量的有向图，每条边存储正向边和反向边。
2. 寻找增广路：每次使用 $\text{SPFA}$ 寻找从源点到汇点的最短路径（按费用计算），同时记录路径。
3. 更新流量：沿找到的增广路增加流量，更新边的残余容量，并累加费用。
4. 重复：直到无法找到增广路或流量达到 $2$ 为止。
5. 判断结果：若最终流量为 $2$ ，输出总费用；否则输出 Back to jail。

代码实现

// Dijkstra Dijkstra
// UVa ID: 10806
// Verdict: Accepted
// Submission Date: 2017-10-05
// UVa Run Time: 0.000s
//
// 版权所有（C）2017，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>

using namespace std;

const int MAXV = 110, MAXE = 20100, INF = 0x3f3f3f3f;

// 弧结构体：表示网络流中的一条边
struct arc { 
    int u, v, capacity, residual, cost, next; 
} arcs[MAXE];

int idx, source, sink, dist[MAXV], head[MAXV], parent[MAXV], visited[MAXV];
int n, m, fee, flow; // fee：总费用，flow：总流量

// SPFA 算法寻找最短增广路（按费用）
bool spfa() {
    for (int i = 0; i < MAXV; i++)
        dist[i] = INF, parent[i] = -1, visited[i] = 0;
    dist[source] = 0, visited[source] = 1;
    queue<int> q; q.push(source);
    while (!q.empty()) {
        int u = q.front(); q.pop(); visited[u] = 0;
        for (int i = head[u]; ~i; i = arcs[i].next) {
            arc e = arcs[i];
            // 如果残余容量大于0且可以松弛
            if (e.residual > 0 && dist[e.v] > dist[u] + e.cost) {
                dist[e.v] = dist[u] + e.cost;
                parent[e.v] = i; // 记录路径
                if (!visited[e.v]) {
                    q.push(e.v);
                    visited[e.v] = 1;
                }
            }
        }
    }
    return dist[sink] < INF; // 如果汇点可达，说明找到增广路
}

// 添加一条从 u 到 v 的弧，容量为 capacity，费用为 cost
void addArc(int u, int v, int capacity, int cost) {
    // 正向弧
    arcs[idx] = (arc){u, v, capacity, capacity, cost, head[u]};
    head[u] = idx++;
    // 反向弧
    arcs[idx] = (arc){v, u, capacity, 0, -cost, head[v]};
    head[v] = idx++;
}

// 最小费用最大流主函数
void mcmf() {
    fee = flow = 0;
    // 每次寻找增广路
    while (spfa()) {
        int delta = INF;
        // 计算增广路上的最小残余容量
        for (int i = parent[sink]; ~i; i = parent[arcs[i].u])
            delta = min(delta, arcs[i].residual);
        flow += delta; // 增加流量
        fee += delta * dist[sink]; // 增加费用
        // 更新残余网络
        for (int i = parent[sink]; ~i; i = parent[arcs[i].u]) {
            arcs[i].residual -= delta;
            arcs[i ^ 1].residual += delta;
        }
    }
}

int main(int argc, char *argv[]) {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    while (cin >> n, n > 0) {
        cin >> m;
        idx = 0, source = 0, sink = n;
        memset(head, -1, sizeof(head));
        // 读入无向边，转化为两条有向弧
        for (int i = 1, u, v, t; i <= m; i++) {
            cin >> u >> v >> t;
            addArc(u, v, 1, t);
            addArc(v, u, 1, t);
        }
        // 添加超级源点到节点1的弧，容量为2，表示需要两条路径
        addArc(0, 1, 2, 0);
        mcmf();
        if (flow < 2) cout << "Back to jail\n";
        else cout << fee << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：每次 $\text{SPFA}$ 寻找增广路的时间复杂度为 $O(VE)$ ，由于最多增广 $2$ 次（流量需求为 $2$ ），总时间复杂度约为 $O(VE)$ 。在本题限制下（$n\le 100,m\le n(n-1)/2$），完全可行。
• 空间复杂度：主要存储图的结构，为 $O(V+E)$ 。

总结

本题通过将边不相交最短双路径问题转化为最小费用最大流问题，巧妙地利用了网络流模型中的容量限制来保证边的不重复使用。实现上使用了经典的 $\text{SPFA}$ 算法求解最小费用流，代码简洁高效。需要注意的是，无向图需拆分为两条有向边，并正确设置反向弧的容量和费用。