Day 077-Q5 | Steiner Tree on General Graph

問題

$N$ 頂点 $M$ 辺の無向重み付きグラフが与えられる。$K$ 個の必須頂点 $v_1, v_2, \ldots, v_K$ が指定されている。これら $K$ 個の頂点をすべて含む連結部分グラフのうち、辺の重みの和が最小のものを求め、その値を出力せよ（最小シュタイナー木問題）。

制約

パラメータ	範囲	備考
$N$	$2 \le N \le 100$	頂点数
$M$	$1 \le M \le 500$	辺数
$K$	$2 \le K \le 10$	必須頂点数（小さいことが重要）
$w_i$	$1 \le w_i \le 10^6$	辺重み
グラフ	連結	孤立頂点なし

入出力例

入力例1

出力例1

必須頂点 {1,3,5}。最小シュタイナー木: 辺 1-2(1), 2-3(2), 3-5(3) で合計 7。または 1-3(4)+3-5(3)=7 も同コスト。

概念図: 最小シュタイナー木と DP

橙色の辺が最適シュタイナー木（コスト合計 7）。DP は「必須頂点の部分集合 $S$ を含む、頂点 $v$ を含む連結グラフの最小コスト」を管理。

ヒント

ヒント1（方向性）

最小シュタイナー木は一般に NP 困難だが、$K \le 10$ の場合は $O(3^K \cdot N + 2^K \cdot M \log N)$ のビット DP が知られている。

ヒント2（アプローチ）

Dreyfus-Wagner アルゴリズム:
$dp[S][v]$ = 必須頂点の部分集合 $S$ を全て含む、頂点 $v$ を含むシュタイナー木の最小コスト
遷移1: 集合分割 $dp[S][v] = \min_{T} (dp[T][v] + dp[S \setminus T][v])$
遷移2: Dijkstra で辺を通じて伝播

ヒント3（ほぼ答え）

for s in range(1, 1 << K):
    # 集合の分割
    sub = (s - 1) & s
    while sub > 0:
        for v in range(N):
            dp[s][v] = min(dp[s][v], dp[sub][v] + dp[s ^ sub][v])
        sub = (sub - 1) & s
    # Dijkstra で辺を通じて更新
    dijkstra(dp[s], graph)

模範解答

import sys
import heapq
input = sys.stdin.readline
INF = float('inf')

def solve():
    N, M, K = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        u -= 1; v -= 1
        graph[u].append((v, w))
        graph[v].append((u, w))

    terminals = list(map(lambda x: int(x)-1, input().split()))

    dp = [[INF] * N for _ in range(1 << K)]
    for i in range(K):
        dp[1 << i][terminals[i]] = 0

    def dijkstra(dist):
        hq = [(dist[v], v) for v in range(N) if dist[v] < INF]
        heapq.heapify(hq)
        while hq:
            d, u = heapq.heappop(hq)
            if d > dist[u]:
                continue
            for v, w in graph[u]:
                nd = dist[u] + w
                if nd < dist[v]:
                    dist[v] = nd
                    heapq.heappush(hq, (nd, v))

    for s in range(1, 1 << K):
        sub = (s - 1) & s
        while sub > 0:
            for v in range(N):
                val = dp[sub][v] + dp[s ^ sub][v]
                if val < dp[s][v]:
                    dp[s][v] = val
            sub = (sub - 1) & s
        dijkstra(dp[s])

    print(min(dp[(1 << K) - 1]))

solve()

Step-by-Step 解説

Step 1: 状態定義

$dp[S][v]$ = 必須頂点の部分集合 $S$ を全て含む連結部分グラフで、頂点 $v$ を含むものの最小辺重み和。$v$ は「木の根」ではなく「この木に含まれる任意の頂点」。

Step 2: 初期化

$dp[\{i\}][t_i] = 0$（単一の必須頂点 $i$ のみを含む部分木）、それ以外は $\infty$。

Step 3: 遷移1（集合の分割）

$S$ を二つの非空な真部分集合 $T$ と $S \setminus T$ に分けて、頂点 $v$ を共有して二つのシュタイナー木をマージ:

$$dp[S][v] = \min_{T \subsetneq S, T \neq \emptyset} \left( dp[T][v] + dp[S \setminus T][v] \right)$$

Step 4: 遷移2（Dijkstra）

集合 $S$ を固定したまま、辺を通じてコストを伝播（中継点を追加して木を延ばす操作）:

$$dp[S][v] \leftarrow \min(dp[S][v], dp[S][u] + w(u, v))$$

Step 5: 計算量

フェーズ	計算量
集合分割（全 $S$）	$O(3^K \cdot N)$
Dijkstra（全 $S$）	$O(2^K \cdot (N + M) \log N)$
合計	$O(3^K \cdot N + 2^K \cdot M \log N)$

$K \le 10, N \le 100, M \le 500$: $3^{10} \times 100 + 2^{10} \times 500 \times 7 \approx 6 \times 10^6$ で十分高速。

よくあるミス

ミス	原因	正しい書き方
部分集合列挙で無限ループ	`sub = (sub-1) & s` が `sub=0` を通過	`while sub > 0:` の条件
初期化ミス	デフォルト 0 と混同	全て `INF` で初期化後、terminal のみ 0
Dijkstra の順序ミス	分割の前に Dijkstra を呼ぶ	分割 → Dijkstra の順番
terminal のみで min を取る	中継点を見逃す	`min(dp[full][v] for v in range(N))`

次のステップ

発展問題: 必須頂点数 $K > 10$ の場合（メトリック閉包 + 近似解、Zelikovsky の 11/6-近似）
応用: 有向グラフ上の Steiner Tree（コスト最小の有向部分グラフで全必須頂点到達）

Day 077-Q5 — Steiner Tree on General Graph（最小シュタイナー木・Dreyfus-Wagner ビット DP）

問題

制約