Day 107-Q2 — Directed Steiner Tree（有向シュタイナー木）

2026-07-30 赤色 Master / Phase 8+ ★★★★★★★★★ 端末部分集合DP + 逆辺Dijkstra緩和

問題

$N$頂点$M$辺の重み付き有向グラフが与えられる。根$r$と$K$個の端末（ターミナル）頂点$t_1,\dots,t_K$が指定される（根が端末に含まれてもよい）。

根$r$を根とする有向全域木（arborescence）の部分グラフであって、全ての端末に$r$から到達できるもののうち、辺の重みの総和が最小のものを求めよ（存在しなければ-1）。これは無向グラフの通常のシュタイナー木問題の有向グラフ版であり、Dreyfus-Wagner法を有向グラフに一般化したアルゴリズムで解く。

入力形式

N M K
r
t_1 t_2 ... t_K
u_1 v_1 w_1
...
u_M v_M w_M

制約

$1 \le N \le 15$
$0 \le M \le N(N-1)$
$1 \le K \le 10$
$1 \le w_i \le 1000$

入出力例

入力例1

5 6 3
1
2 4 5
1 2 3
2 3 2
1 3 10
3 4 1
2 5 7
4 5 1

出力例1

7

根1から辺重み3で頂点2、辺重み2で頂点3、辺重み1で頂点4へ辿ると端末2,4に到達でき、さらに辺重み1で頂点4から頂点5へ辿れば端末5にも到達できる。合計 $3+2+1+1=7$ が最小。

概念図: 端末部分集合DPの2段遷移

dp[mask][v]: vを根としてmaskの端末を全カバーする最小コスト 遷移1: 分岐(マージ) v dp[sub][v] dp[mask^sub][v] 同じ頂点vで2つの端末部分集合を合流 遷移2: 辺の追加(根の付替え) u v w(u,v) dp[mask][u] = min(dp[mask][u], w(u,v)+dp[mask][v]) → 逆辺グラフ上のDijkstraで一括処理 maskをpopcountの小さい順(=整数の昇順)に処理し、各maskで「分岐→Dijkstra確定」の2段階を行う 計算量: O(3^K・N + 2^K・N log N)

ヒント（段階的開示）

ヒント1: 方向性
端末が2つなら「根から各端末への最短路の和」で十分そうに見えるが、端末が3つ以上になると複数の端末への経路が共通の枝を共有した方が安い場合がある。どの中間頂点で経路を分岐させるべきかを全探索すると指数時間になるため、部分集合を状態に持つDPが必要になる。
ヒント2: アプローチ
$dp[\text{mask}][v]$を「頂点$v$を根とする部分木で端末集合maskを全てカバーする最小コスト」と定義する。2種類の遷移がある：(1)分岐＝同じ頂点$v$で端末集合を2つの排反な部分集合に分けそれぞれ別の部分木でカバーし$v$で合流：$dp[\text{mask}][v]=\min_{s\subsetneq \text{mask}} dp[s][v]+dp[\text{mask}\setminus s][v]$。(2)辺の追加＝頂点$u$から辺$u\to v$を1本足す：$dp[\text{mask}][u]=\min(dp[\text{mask}][u], w(u,v)+dp[\text{mask}][v])$。この遷移は「maskを固定した状態でグラフ全体にDijkstraを1回走らせる」ことと等価（逆辺グラフ上でDijkstraを行うのが実装上自然）。
ヒント3: 誘導（コード骨格） 
for mask in range(1, 1 << K):
    # 1. 分岐: 排反な部分集合ペアを列挙して合流
    sub = (mask - 1) & mask
    while sub > 0:
        other = mask ^ sub
        if sub >= other:  # 重複計算を避ける
            for v in range(N):
                dp[mask][v] = min(dp[mask][v], dp[sub][v] + dp[other][v])
        sub = (sub - 1) & mask
    # 2. 辺の追加: 逆辺グラフでdp[mask][*]を初期距離とするDijkstra
    # heapqで(dp[mask][v], v)を初期値にpushし、radjで緩和する

模範解答 (Python)

import sys, heapq

INF = float('inf')

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    r = int(data[idx]) - 1; idx += 1
    terms = []
    for _ in range(K):
        terms.append(int(data[idx]) - 1); idx += 1
    radj = [[] for _ in range(N)]
    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        w = int(data[idx]); idx += 1
        radj[v].append((u, w))  # 元の辺 u->v を「vからuへの逆辺」として保持

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

    for mask in range(1, 1 << K):
        sub = (mask - 1) & mask
        while sub > 0:
            other = mask ^ sub
            if sub < other:
                sub = (sub - 1) & mask
                continue
            dm, do = dp[sub], dp[other]
            row = dp[mask]
            for v in range(N):
                if dm[v] < INF and do[v] < INF:
                    val = dm[v] + do[v]
                    if val < row[v]:
                        row[v] = val
            sub = (sub - 1) & mask

        row = dp[mask]
        pq = [(row[v], v) for v in range(N) if row[v] < INF]
        heapq.heapify(pq)
        visited = [False] * N
        while pq:
            d, u = heapq.heappop(pq)
            if visited[u]:
                continue
            visited[u] = True
            if d > row[u]:
                continue
            for u2, w in radj[u]:
                nd = d + w
                if nd < row[u2]:
                    row[u2] = nd
                    heapq.heappush(pq, (nd, u2))

    ans = dp[full][r]
    print(ans if ans < INF else -1)


solve()
計算量: $O(3^K N + 2^K N\log N)$（部分集合の分岐列挙が$3^K$のペア数、Dijkstraが各maskで$O(N\log N)$）。ランダム300ケースでbrute-force全探索と一致することを確認済み。

Step-by-Step 解説

1DPの定義と初期化
$dp[\text{mask}][v]$を「vを根としてmaskの端末を全てカバーする最小コスト」と定義。端末$t_i$自身は$dp[2^i][t_i]=0$で初期化。
2分岐遷移は部分集合の列挙で行う
maskの空でない真部分集合subを列挙し、other=mask^subとの組で合流を試す。sub<otherで片方だけ処理し重複計算を省く。
3辺1本の追加は逆辺グラフの多始点Dijkstraで確定
「maskを固定したまま辺u→vを使ってvの良い値をuに伝える」遷移は、dp[mask][*]を初期距離とする最短路問題。逆辺グラフ上で多始点Dijkstraを行えば正しく確定する。
4maskの処理順序が正しさの鍵
maskを整数の昇順に処理すれば、分岐遷移で参照するsub, otherは必ずmaskより真に小さく、既にDijkstraまで確定済みであることが保証される。

よくあるミス

ミス原因正しい書き方
Dijkstraの緩和を元のグラフの向きのまま行う「vの良い値を辺u→v経由でuに伝える」向きと逆になる逆辺グラフ（radj[v]に元の辺u→vを「vからu」として登録）で緩和する
分岐遷移でsubとotherを両方処理してしまう同じペアを2回計算し計算量が倍になるsub < otherのときはスキップし片方のみ処理する
dp[mask]の初期値がINFの頂点をDijkstraの初期ヒープに入れる無駄な処理が走り遅くなるdp[mask][v] < INFの頂点のみ初期ヒープに入れる
根rが端末に含まれる場合の初期化を見落とす対応するdp[1<<i][r]=0が効いていることに気づかない端末リストに根が含まれるなら自動的に初期化されることを確認する

次のステップ

  • 発展: 辺コストだけでなく頂点コストも考慮する（頂点を通過するたびにコストがかかる版）
  • 発展: Kが大きい場合の近似アルゴリズム（$O(\log K)$近似が知られている、貪欲法ベース）
  • 次回予告: Fractional Cascading（複数ソート済み配列への一括successorクエリ）

自己評価

自分の回答

気づき・メモ