ABC 395 G — Minimum Steiner Tree 2

考察

非負edgeのconnected subgraph最小costはSteiner treeであり、必須terminalは固定1..Kにquery固有s,tを加えたもの。K≤8なのでfixed terminal subset DPが使える。dp[mask][v]をmask terminalsとvを結ぶ最小costとすると、vで二treeを結ぶsubset mergeと、endpointをedge沿いに移すshortest-path closureの二段階で更新できる。同じroot vでmaskをzとmask\zに分けるdp[z][v]+dp[mask\z][v]がbranch結合を表す。merge遷移を確定後、dp[mask][*]を初期距離とするmulti-source shortest pathで任意Steiner vertexまで延長する。

採用する候補: Dreyfus–Wagner型subset Steiner DPを、固定terminal集合+各sを追加した状態まで前計算する

必要maskは固定K terminalに高々一query頂点を加えたものに整理でき、密graphのO(N²) Dijkstra closureとsubset mergeでO(3^K N²+2^K N³)に収まる。

棄却する候補: 各queryごとにK+2 terminalのSteiner DPを独立に実行する

Q≤5000で同じ固定terminal部分の計算を繰り返し、指数DPをquery数倍する。

固定terminal bitmaskについてsubset merge→dense Dijkstra closureを昇順maskで計算する。さらに各s>Kを一つ追加したterminal stateを同じ遷移で計算し、そのstateからtへclosureしたdp値をquery答えとして参照する。

典型の発動条件

subset Steiner tree DP

発動条件: terminal数が小さく、Steiner vertexを自由に使える最小connected subgraphを求めるとき。

terminal subsetと接続rootを状態にする。

subset merge+shortest-path closure

発動条件: Steiner treeのbranch結合とedge延長を分離するとき。

submask partition後にDijkstraでroot位置を緩和する。

query共通部分の前計算

発動条件: 多数queryが大半のterminalを共有するとき。

固定K集合と追加sごとまでを共有計算する。

問題固有の要素

queryの二terminal s,tを同時にsubset bitへ加えず、sをterminal集合へ入れてtを最終root位置として読むとquery pair全体を前計算できる。

別の問題へ持ち帰る視点: 小さい固定集合+二可変endpointの問題では、一方を状態生成軸、他方を全頂点closureの参照先にする。

正当性

固定端点集合と s を結ぶ木を root t で読むことは、固定端点・s・t を結ぶ問題と同値であり、tに別のbitは不要。subset merge と最短路 closure は root 付き Steiner 木の分岐と枝延長を網羅する。可変 s の bit を含む状態では、併合の一方だけが s を含み、他方は共有済み固定 subset DP となる。端点数の帰納法で全追加 s の最適値を求め、一度の計算を全 t で共有できる。

実装上の注意

  • Cはtriangle inequalityを満たすとは限らないので元complete edgeでclosureを必ず行う。submask重複は正しさを保つが計算量を見積もる。

復習の核

  • N≤9,K≤3でedge subset全探索または全Steiner vertex subsetのMSTと比較し、s/tが中継点として使われるcaseを確認する。

計算量と制約

時間

N 頂点 complete graph、固定端点 K、Q 質問。固定集合+各 s の共有前計算で O(3^K N²+2^K N³+Q)。

空間

固定 subset と追加 s の dp を全保持すると O(2^K N²)、答え pair 表 O(N²)。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 3 \leq N \leq 80; 1\leq K\leq \min(N-2,\textcolor{red}{8}); 0 \leq C_{i,j} \leq 10^9 \ (1 \leq i,j \leq N, i \ne j); C_{i,j} = C_{j,i} \ (1 \leq i,j \leq N, i \ne j); C_{i,i} = 0 \ (1 \leq i \leq N); 1 \leq Q \leq 5000; K+1 \leq s_i, t_i \leq N \ (1 \leq i \leq Q); s_i \ne t_i \ (1 \leq i \leq Q); All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Minimum Steiner Tree 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: Steiner tree subset DP

主題
  • Steiner tree subset DP: terminal subsetと終点を状態に、subset分割mergeとmulti-source shortest path relaxationを交互に行う。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
    • 最短路モデル: 非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。

    主タグ: Steiner tree subset DP

    補助タグ: 最短路モデル

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: Steiner tree subset DP

    • terminal subsetと終点を状態に、subset分割mergeとmulti-source shortest path relaxationを交互に行う。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • 部分集合・bitmask状態DP — DPの最小十分状態で得た考え方と実装を再利用し、部分集合・bitmask状態DPの発動条件・正当化・境界を重複なく学ぶ。
    • 最短路モデル — 基本的な明示グラフ探索を土台に、辺重みに応じた緩和・距離確定順を選び、最短距離と計算量を求める。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題