Day 044-Q1 | 最小シュタイナー木（Dreyfus-Wagner bitDP）

問題

$N$ 頂点 $M$ 辺の重み付き無向連結グラフが与えられる。指定された $K$ 個のターミナル頂点 $t_1,\dots,t_K$ をすべて連結にする部分グラフのうち、辺重み総和が最小となるもの（最小シュタイナー木）の重みを求めよ。ターミナル以外の中間頂点（Steiner点）を任意に含んでよい。

制約

$1 \le N \le 100$

$1 \le M \le N(N-1)/2$

$1 \le K \le 10$

$1 \le w_i \le 10^6$

グラフは連結

入出力例

入力例 1

出力例 1

概念図: 部分集合マージ + 辺緩和

ヒント（段階的開示）

ヒント1: 方向性

ターミナルが $K \le 10$ と少ない。ターミナル集合の部分集合をビットで表現する bitDP が定石。$dp[S][v]$ = 「集合 $S$ のターミナルを頂点 $v$ を根として連結にする最小コスト」。

ヒント2: アプローチ

部分集合マージ: $dp[S][v] = \min_{T \subsetneq S} dp[T][v] + dp[S \setminus T][v]$
辺緩和 (Dijkstra): $dp[S][v] = \min_u dp[S][u] + \mathrm{dist}(u, v)$

ヒント3: 実装骨格

for S in range(1, 1<<K):
    sub = (S-1) & S
    while sub:
        other = S ^ sub
        if sub < other:
            for v: dp[S][v] = min(dp[S][v], dp[sub][v]+dp[other][v])
        sub = (sub-1) & S
    # 各 S で multi-source Dijkstra

計算量 $O(3^K N + 2^K (N+M)\log N)$。

模範解答 (Python)

import sys
import heapq

def solve():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, w = map(int, input().split())
        g[u].append((v, w))
        g[v].append((u, w))
    terms = list(map(int, input().split()))

    INF = float('inf')
    full = 1 << K
    dp = [[INF] * (N + 1) for _ in range(full)]
    for i, t in enumerate(terms):
        dp[1 << i][t] = 0

    for S in range(1, full):
        sub = (S - 1) & S
        while sub > 0:
            other = S ^ sub
            if sub < other:
                for v in range(1, N + 1):
                    if dp[sub][v] < INF and dp[other][v] < INF:
                        c = dp[sub][v] + dp[other][v]
                        if c < dp[S][v]:
                            dp[S][v] = c
            sub = (sub - 1) & S

        pq = []
        for v in range(1, N + 1):
            if dp[S][v] < INF:
                heapq.heappush(pq, (dp[S][v], v))
        while pq:
            d, v = heapq.heappop(pq)
            if d > dp[S][v]:
                continue
            for to, w in g[v]:
                nd = d + w
                if nd < dp[S][to]:
                    dp[S][to] = nd
                    heapq.heappush(pq, (nd, to))

    print(min(dp[full - 1][v] for v in range(1, N + 1)))

solve()

Step-by-Step 解説

1状態定義
$dp[S][v]$ = ターミナル部分集合 $S$ を頂点 $v$ を含む連結部分木で結ぶ最小コスト。$v$ はターミナルでもSteiner点でもよい。

2初期化
単一ターミナル $\{i\}$ では根を $t_i$ に置けばコスト0。dp[1<<i][terms[i]] = 0。

3部分集合マージ
同じ根 $v$ を共有する2部分木を合体。部分集合列挙 sub=(sub-1)&S。全体 $O(3^K N)$。

4辺緩和 (Dijkstra)
根を隣接頂点へ伸ばす操作は最短路に相当。各 $S$ で multi-source Dijkstra を回す。

5答え
全ターミナル集合 $S=2^K-1$ で任意の根 $v$ の最小値。

計算量

部分集合マージ: $O(3^K N)$
辺緩和: $O(2^K (N + M)\log N)$
合計: $O(3^K N + 2^K (N+M)\log N)$
空間: $O(2^K N)$

よくあるミス

ミス	原因	正しい書き方
部分集合を二重カウント	$T$ と $S\setminus T$ 両方処理	`if sub < other` で片側のみ
辺緩和を省略	マージのみでは木が伸びない	各 $S$ で Dijkstra 実行
$3^K$ の計算量を誤認	$2^K \cdot 2^K$ と誤見積もり	$\sum_S 2^{\|S\|}=3^K$
INF同士の加算	int では巨大値	加算前にINFチェック

次のステップ

発展問題: Group Steiner Tree（ターミナルがグループ・NP困難の近似）
類題: ABC 364-G、ICPC地区予選のシュタイナー木
応用: ネットワーク配線最小化、VLSI設計

自己評価

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