CSU 1506 Double Shortest Paths：最小費用最大流建模

題目大意

• 有向圖，n 點，m 條邊。
• 兩人從 1 走到 n，第一次通過邊費用 d_i，第二次通過同一邊費用 d_i + a_i。
• 求兩人到達 n 的最小總費用。

網絡流建模

1. 每條原邊拆為兩條平行邊：
    容量 1，費用 d_i（第一次通行）。
    容量 1，費用 d_i + a_i（第二次通行）。
2. 加超級源點 S 連向 1（容量 2，費用 0），n 連向超級匯點 T（容量 2，費用 0）。
3. 跑最小費用最大流，流量為 2 時的最小費用即為答案。

SPFA + 最小費用最大流模板

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
struct Edge { int to, rev, cap, cost; };
vector G[610];
void addEdge(int u, int v, int cap, int cost) {
    G[u].push_back({v, (int)G[v].size(), cap, cost});
    G[v].push_back({u, (int)G[u].size()-1, 0, -cost});
}
pair minCostMaxFlow(int s, int t, int maxf) {
    int n = 610, flow = 0, cost = 0;
    vector dist(n), pv(n), pe(n);
    while (flow < maxf) {
        fill(dist.begin(), dist.end(), INF);
        vector inq(n, false);
        queue q;
        dist[s] = 0; q.push(s); inq[s] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop(); inq[u] = false;
            for (int i = 0; i < 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;
        }
        flow += addf;
        cost += addf * dist[t];
    }
    return {flow, cost};
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        for (int i = 0; i < 610; ++i) G[i].clear();
        int S = 0, T = n + 1;
        addEdge(S, 1, 2, 0);
        addEdge(n, T, 2, 0);
        for (int i = 0; i < m; ++i) {
            int u, v, d, a; cin >> u >> v >> d >> a;
            addEdge(u, v, 1, d);
            addEdge(u, v, 1, d + a);
        }
        auto res = minCostMaxFlow(S, T, 2);
        cout << res.second << "\n";
    }
    return 0;
}

複雜度

• 節點 ≤ 102，邊 ≤ 2×75×2 + 4 ≈ 304。
• SPFA 平均 O(E)，流量 2，極快。