Day 089-Q1 — Suurballe's Algorithm（辺素な最短路対・MCMF + ポテンシャル法）

問題

$N$ 頂点 $M$ 辺の有向グラフが与えられる。各辺 $i$ は頂点 $u_i$ から $v_i$ へ向かう重み $w_i$（非負整数）の辺である。頂点 $s$ から頂点 $t$ へ向かう辺素な（同じ辺を2度使わない）2本の経路を選び、その長さの合計を最小化せよ。そのような2本の経路が存在しない場合は -1 を出力せよ。

入出力例

4 5
1 2 1
2 4 1
1 3 2
3 4 1
2 3 1
1 4

5

2 1
1 2 5
1 2

-1

例1: 経路 $1\to2\to4$（長さ2）と $1\to3\to4$（長さ3）が辺を共有せず合計5。例2: 辺が1本しかなく2本の辺素な経路は作れない。

概念図: 残余グラフ上で2回目の増加路を探し、重なり部分を打ち消す

ヒント

def add_edge(u, v, w):
    graph[u].append(len(edge_to)); edge_to.append(v); edge_cap.append(1); edge_cost.append(w)
    graph[v].append(len(edge_to)); edge_to.append(u); edge_cap.append(0); edge_cost.append(-w)
# ダイクストラを reduced cost = w(u,v)+h[u]-h[v] で2回実行し、合計コストを求める

模範解答

import sys, heapq

def main():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    edges_in = []
    for _ in range(m):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        edges_in.append((u, v, w))
    s = int(data[idx]); idx += 1
    t = int(data[idx]); idx += 1

    INF = float('inf')
    graph = [[] for _ in range(n + 1)]
    edge_to, edge_cap, edge_cost = [], [], []

    def add_edge(u, v, w):
        graph[u].append(len(edge_to)); edge_to.append(v); edge_cap.append(1); edge_cost.append(w)
        graph[v].append(len(edge_to)); edge_to.append(u); edge_cap.append(0); edge_cost.append(-w)

    for u, v, w in edges_in:
        add_edge(u, v, w)

    dist = [INF] * (n + 1); dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for eid in graph[u]:
            v = edge_to[eid]
            if edge_cap[eid] > 0 and d + edge_cost[eid] < dist[v]:
                dist[v] = d + edge_cost[eid]
                heapq.heappush(pq, (dist[v], v))
    h = [0] * (n + 1)
    for v in range(1, n + 1):
        if dist[v] < INF:
            h[v] = dist[v]

    total_flow = 0
    total_cost = 0
    for _ in range(2):
        dist = [INF] * (n + 1); dist[s] = 0
        prevedge = [-1] * (n + 1)
        pq = [(0, s)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            for eid in graph[u]:
                v = edge_to[eid]
                if edge_cap[eid] > 0:
                    nd = d + edge_cost[eid] + h[u] - h[v]
                    if nd < dist[v]:
                        dist[v] = nd
                        prevedge[v] = eid
                        heapq.heappush(pq, (nd, v))
        if dist[t] == INF:
            break
        for v in range(1, n + 1):
            if dist[v] < INF:
                h[v] += dist[v]
        v = t
        path = []
        while v != s:
            eid = prevedge[v]
            path.append(eid)
            v = edge_to[eid ^ 1]
        step_cost = 0
        for eid in path:
            edge_cap[eid] -= 1
            edge_cap[eid ^ 1] += 1
            step_cost += edge_cost[eid]
        total_flow += 1
        total_cost += step_cost

    print(total_cost if total_flow >= 2 else -1)

main()

計算量: ダイクストラを合計3回（初期ポテンシャル1回＋増加路探索2回）実行するので $O(M\log N)$。

Step-by-Step 解説

Step 1: 容量1・費用=重みのグラフとして定式化

$s\to t$ に流量2を最小費用で流せれば、流量保存則より辺を共有しない2本の経路に自然に分解できる。

Step 2: 初期ポテンシャルをダイクストラで求める

重みが非負なので1回目は通常のダイクストラで求まり、これをポテンシャル $h$ とする。

Step 3: reduced cost でダイクストラを繰り返す

残余グラフの逆辺の費用は負になるが、reduced cost $w(u,v)+h[u]-h[v]$ は常に非負に保たれる（Johnson's technique）。

Step 4: 増加路に沿って流し、ポテンシャルを更新

h[v] += dist[v] で更新し、次のイテレーションに備える。

Step 5: 2回とも増加できれば合計コストが答え

逆辺を通ることによる負のコスト加算＝重複部分の打ち消しが正しく反映される。

よくあるミス

次のステップ

• 発展問題: $k$ 本の辺素な最短路の合計を最小化する一般化
• 発展問題: 頂点素（vertex-disjoint）な2経路を求める版

自己評価