UVA 1658 Admiral：最小費用最大流求兩條不相交最短路

問題轉化

求從 1 到 n 的兩條邊不相交的路徑，總長度最小。
等價於：每條邊容量 1，費用為長度，源 1 匯 n，跑最小費用流流量 2。

拆點技巧（可選）

若點也不能重複（除源匯），將每點 i 拆為 i_in, i_out，中間連容量 1 費用 0 的邊。

SPFA/最小費用最大流模板

struct MCMF {
    struct Edge { int to, rev, cap, cost; };
    vector> G;
    vector dist, pv, pe; vector inq;
    void addEdge(int u, int v, int cap, int cost) { ... }
    bool spfa(int s, int t) { ... }
    pair maxflow(int s, int t, int maxf) { ... }
};

完整代碼框架

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct MCMF {
    struct Edge { int to, rev, cap, cost; };
    vector> G;
    MCMF(int n) : G(n) {}
    void addEdge(int u, int v, int cap, int cost) {
        Edge a{v, (int)G[v].size(), cap, cost};
        Edge b{u, (int)G[u].size(), 0, -cost};
        G[u].push_back(a); G[v].push_back(b);
    }
    pair minCostMaxFlow(int s, int t, int maxf) {
        int flow = 0, cost = 0;
        vector dist(G.size()), pv(G.size()), pe(G.size());
        vector inq(G.size());
        while (flow < maxf) {
            fill(dist.begin(), dist.end(), INF);
            dist[s] = 0; queue q; q.push(s); inq[s] = true;
            while (!q.empty()) {
                int u = q.front(); q.pop(); inq[u] = false;
                for (int i = 0; i < (int)G[u].size(); ++i) {
                    Edge &e = G[u][i];
                    if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
                        dist[e.to] = dist[u] + e.cost;
                        pv[e.to] = u; pe[e.to] = i;
                        if (!inq[e.to]) { q.push(e.to); inq[e.to] = true; }
                    }
                }
            }
            if (dist[t] == INF) break;
            int addf = maxf - flow;
            for (int v = t; v != s; v = pv[v])
                addf = min(addf, G[pv[v]][pe[v]].cap);
            for (int v = t; v != s; v = pv[v]) {
                Edge &e = G[pv[v]][pe[v]];
                e.cap -= addf; G[v][e.rev].cap += addf;
                cost += e.cost * addf;
            }
            flow += addf;
        }
        return {flow, cost};
    }
};
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        MCMF mcmf(n+1);
        for (int i = 0; i < m; ++i) {
            int u, v, c; cin >> u >> v >> c;
            mcmf.addEdge(u, v, 1, c);
            mcmf.addEdge(v, u, 1, c);
        }
        auto [flow, cost] = mcmf.minCostMaxFlow(1, n, 2);
        if (flow < 2) cout << "Back to jail\n";
        else cout << cost << '\n';
    }
    return 0;
}

複雜度

SPFA 平均 O(E)，流量 2 只需增廣兩次，極快。