Day 028-Q2 | 最小有向全域木（Chu-Liu/Edmonds）

問題

$N$ 頂点 $M$ 辺の有向重み付きグラフが与えられる。指定された根 $r$ からすべての頂点へ到達できる最小有向全域木（MDST: Minimum Directed Spanning Tree）のコストを求めよ。

有向全域木（arborescence）とは、根 $r$ から各頂点への有向パスが一意に存在するような $N-1$ 本の有向辺の集合（根付き木）である。

入力形式

N M r
u_1 v_1 w_1
u_2 v_2 w_2
...
u_M v_M w_M

辺 $(u_i, v_i, w_i)$: $u_i$ から $v_i$ へ重み $w_i$ の有向辺。

制約

$2 \le N \le 100$

$1 \le M \le 10^4$

$1 \le w_i \le 10^6$

根 $r$ から全頂点へ到達可能

入出力例

入力例 1

出力例 1

入力例は理解確認のため数値を設定しているため、最終答えは実装で確認すること。

ヒント (段階的開示)

ヒント1: 方向性

Chu-Liu/Edmonds アルゴリズムは以下のフェーズで動作する。

各頂点（根以外）に対して「最小コストの入辺」を選ぶ
閉路が存在しなければ、その辺集合が答え
閉路が存在すれば、閉路を1頂点に縮約してコストを調整し、再帰的に解く

ヒント2: アプローチ

閉路の縮約（contraction）の際のコスト調整がポイント。閉路内の頂点 $v$ への入辺 $(u, v, w)$ のコストは $w - \text{min\_in}[v]$ に調整する。

ヒント3: 誘導

def min_cost_arborescence(n, root, edges):
    INF = float('inf')
    while True:
        # Step 1: 各頂点の最小入辺を選ぶ
        min_in = [INF] * n
        min_from = [-1] * n
        for u, v, w in edges:
            if v != root and w < min_in[v]:
                min_in[v] = w
                min_from[v] = u
        # Step 2: 閉路検出
        # Step 3: 閉路がなければ終了 / あれば縮約
        ...

模範解答 (Python)

import sys
input = sys.stdin.readline

def min_cost_arborescence(n, root, edges):
    """
    Chu-Liu/Edmonds Algorithm
    Returns the minimum cost of a directed spanning tree rooted at `root`.
    Time: O(EV) for naive, O(E log V) for optimized
    """
    INF = float('inf')
    total_cost = 0

    while True:
        # Step 1: 各頂点（根以外）の最小コスト入辺を選ぶ
        min_in = [INF] * n
        min_from = [-1] * n
        for u, v, w in edges:
            if v != root and w < min_in[v]:
                min_in[v] = w
                min_from[v] = u

        if any(min_in[v] == INF for v in range(n) if v != root):
            return INF

        total_cost += sum(min_in[v] for v in range(n) if v != root)

        # Step 2: 閉路検出
        visited = [-1] * n
        comp = [-1] * n
        num_comp = 0

        for v in range(n):
            if v == root:
                continue
            u = v
            while u != root and visited[u] == -1:
                visited[u] = v
                u = min_from[u]

            if u != root and visited[u] == v:
                cycle_node = u
                while comp[cycle_node] == -1:
                    comp[cycle_node] = num_comp
                    cycle_node = min_from[cycle_node]
                num_comp += 1

        if num_comp == 0:
            break

        for v in range(n):
            if comp[v] == -1:
                comp[v] = num_comp
                num_comp += 1

        # Step 3: 閉路を縮約してグラフを再構築
        new_edges = []
        for u, v, w in edges:
            cu, cv = comp[u], comp[v]
            if cu != cv:
                new_w = w - (min_in[v] if min_in[v] != INF else 0)
                new_edges.append((cu, cv, new_w))

        root = comp[root]
        n = num_comp
        edges = new_edges

    return total_cost

def solve():
    N, M, r = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v, w = map(int, input().split())
        edges.append((u, v, w))

    ans = min_cost_arborescence(N, r, edges)
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)

solve()

Step-by-Step 解説

1アルゴリズムの直観
有向全域木は根から全頂点へのパスが存在する木。各頂点の入次数はちょうど1（根以外）。Kruskal/Prim が無向専用なのに対し、Chu-Liu/Edmonds は有向に特化。

2最小入辺の選択
各頂点 $v$ に対し最小入辺 $(u, v, w)$ を選ぶ。閉路を形成しなければそのまま MDST。

3閉路検出
最小入辺グラフで min_from を辿り、同じ探索セッション内で訪問済み頂点に到達したら閉路。

4閉路の縮約とコスト調整
閉路を1つの超頂点に縮約。外部入辺 $(u, v, w)$ のコストは $w - \text{min\_in}[v]$ に調整。閉路内辺を破棄する分の差分だけ加算される。

5再帰的実行
縮約後のグラフで同じ処理を繰り返す。各反復で閉路数は単調減少。

計算量

反復回数: $O(N)$
各反復の処理: $O(M)$
全体: $O(NM)$
ヒープ最適化版: $O(M \log N)$

よくあるミス

ミス	原因	正しい書き方
根に入辺を許す	根は入辺0本の頂点	`if v != root` で根をスキップ
コスト調整を忘れる	縮約後のコストが不正	`new_w = w - min_in[v]`
縮約後の根の更新忘れ	古い根IDのまま処理	`root = comp[root]`
閉路検出ループの無限ループ	visited 配列の管理ミス	探索セッションID(`visited[u]=v`)で管理
到達不可能ケース未処理	問題保証に甘える	`min_in[v] == INF` をチェック

Day 028-Q2 — 最小有向全域木（Chu-Liu/Edmonds アルゴリズム）

問題