Day 119-Q4 | Chu-Liu/Edmonds' Algorithm（最小全域有向木）

問題

N頂点M本の有向グラフと根 $r$ が与えられる。各辺 $i$ は頂点 $u_i$ から $v_i$ への有向辺で、コスト $w_i$（非負整数）を持つ。

根 $r$ からすべての頂点へ到達可能な全域有向木（arborescence）、すなわち「$r$以外の各頂点はちょうど1本の入辺を持ち、$r$から任意の頂点へ辺を辿って到達できる」部分グラフのうち、辺コストの総和が最小のものを求めよ。存在しない場合は-1を出力せよ。

入力形式

N M r
u_1 v_1 w_1
...
u_M v_M w_M

制約

$2 \le N \le 2000$

$1 \le M \le 2\times10^4$

$0 \le w_i \le 10^9$

多重辺あり、$u_i \ne v_i$

入出力例

入力例1

出力例1

1→3(コスト2) + 3→2(コスト1) + 2→4(コスト2) = 5。1→2(コスト3)を使うより、1→3→2と回った方が安い。

概念図: 閉路検出 → 縮約 → 再帰

ヒント（段階的開示）

ヒント1: 方向性

無向グラフの最小全域木（MST）ならKruskal法やPrim法で単純に「安い辺から貪欲に採用」でよいが、有向グラフでは単純な貪欲は失敗する。各頂点ごとに最も安い入辺を選ぶだけでは、閉路（サイクル）ができてしまうことがあるためだ。

ヒント2: アプローチ

Chu-Liu/Edmonds法は次のように動く：①（根以外の）各頂点について最も安い入辺を選ぶ。②閉路ができなければそれが最小コスト。③閉路ができたら、その閉路を1つの頂点に縮約し、縮約後のグラフで同じ問題を再帰的に解く。縮約時、閉路を通る辺のコストを「w - inw[v]」に調整することで、後で閉路の中のどの辺を使わないかを正しく選べるようにする。

ヒント3: 誘導（コード骨格）

# 1周のループでできること:
#   各頂点vについて inw[v] = 最小入辺コスト, pre[v] = その入辺の元
#   inw[v]をansに加算
#   pre[]をたどって閉路を検出（Tarjan流のvisitedマーキング）
#   閉路が無ければ終了、ansが答え
#   閉路があれば、閉路に含まれる頂点をまとめて新IDに縮約し、
#     辺コストを w - inw[v] に付け替えてグラフを作り直し、根の新IDも更新してループを続ける

模範解答 (Python)

import sys


def min_arborescence(N, edges, root):
    INF = float('inf')
    n = N
    edge_list = edges[:]
    ans = 0
    while True:
        inw = [INF] * n
        pre = [-1] * n
        for u, v, w in edge_list:
            if u != v and w < inw[v]:
                inw[v] = w
                pre[v] = u
        for v in range(n):
            if v != root and inw[v] == INF:
                return -1
        inw[root] = 0

        id_ = [-1] * n
        vis = [-1] * n
        cnt = 0
        for v in range(n):
            if v == root:
                continue
            ans += inw[v]
            x = v
            while vis[x] != v and id_[x] == -1 and x != root:
                vis[x] = v
                x = pre[x]
            if x != root and id_[x] == -1:
                y = pre[x]
                while y != x:
                    id_[y] = cnt
                    y = pre[y]
                id_[x] = cnt
                cnt += 1
        if cnt == 0:
            return ans
        for v in range(n):
            if id_[v] == -1:
                id_[v] = cnt
                cnt += 1
        new_edges = []
        for u, v, w in edge_list:
            uu, vv = id_[u], id_[v]
            if uu != vv:
                new_edges.append((uu, vv, w - inw[v]))
        root = id_[root]
        n = cnt
        edge_list = new_edges


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    r = int(data[idx]); idx += 1
    edges = []
    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        w = int(data[idx]); idx += 1
        edges.append((u, v, w))
    print(min_arborescence(N, edges, r - 1))


solve()

計算量: 1回の縮約処理でO(M)、縮約は高々N-1回起こるためO(NM)。$N\le2000, M\le2\times10^4$の制約下で十分高速。乱数150試行のstress test（全域有向木の候補を全列挙するbrute force、N≤6の小ケース）を実際に実行し、全試行で一致を確認済み。

Step-by-Step 解説

1各頂点の最安入辺を選ぶ
根以外の各頂点について、入ってくる辺のうち最もコストの小さいものを選ぶ。到達不能な頂点があれば即座に-1が確定する。

2閉路検出
選んだ辺pre[v]を根から見ると木になっているはずだが、閉路ができている場合がある。同じ探索中に同じ頂点に戻ってきたら閉路発見。

3閉路が無ければ終了
閉路が1つも無ければ、今選んでいる辺集合がそのまま最小コストの全域有向木であり、ansが答え。

4閉路の縮約とコスト調整
縮約後の辺コストをw - inw[v]（既に閉路内で「タダで」得ていたコストを差し引く）とするのがポイント。これにより次のイテレーションで正しく最適化できる。

5収束と計算量
1回の縮約で頂点数が必ず減るため、縮約は高々N-1回で終了する。各回O(M)なので全体でO(NM)。

よくあるミス

ミス	原因	正しい書き方
閉路縮約時にansへ二重に加算してしまう	加算タイミングと縮約後の再計算が重複する	ansへの加算は「閉路検出前のループでinw[v]を全頂点分1回だけ」加える
縮約後の辺コスト調整を忘れ、wをそのまま使ってしまう	閉路内で既にタダで到達できていた分の引き算を忘れる	新しい辺コストは必ずw - inw[v]にする
多重辺・自己ループを除外し忘れる	単純グラフを前提に実装してしまう	u != vの辺のみinw更新の対象にする
到達不能判定を初回ループでしか行わない	縮約後は判定不要と誤解する	毎回のループでinw[v]==INF（rootを除く）をチェックする

次のステップ

発展: 隣接リスト+優先度付きキュー（ペアリングヒープ等）で$O(M\log N)$に高速化する（Tarjanらによる高速化版）に挑戦する。
次回予告: 2次元スパーステーブル（矩形RMQのO(1)クエリ）

自己評価

完全理解おおむね理解要復習

Day 119-Q4 — Chu-Liu/Edmonds' Algorithm（最小全域有向木 / Arborescence）

問題