ABC 364 G — Last Major City

考察

固定された主要都市をつなぐ部分と、最後に追加する都市までの接続を分けて考える。固定都市の部分集合と「そこまでつないだ接続点」を状態にすれば、同じ点で二つの部分解を合成する操作と、接続点を道路に沿って移す操作で木を組み立てられる。接続点を全都市について求めておけば、追加都市ごとに計算をやり直す必要はない。

以降、都市を頂点、道路を辺、拡張費用を辺の重みと呼ぶ。必ずつなぐ頂点を端点(terminal)と呼び、固定端点数を k=K−1k=K-1 とする。重みは正なので、必要な頂点をつなぐ連結部分グラフから閉路を取り除けば、費用を増やさず木にできる。このように、端点以外の頂点も中継に使ってよい最小の木が最小シュタイナー木である。

辺集合や中継点集合を直接列挙するには、頂点数も辺数も多すぎる。一方、固定端点は最大9個しかない。そこで「どの固定端点をつないだか」をbitmaskで持ち、木を合成するための接続点を一つ添える。

都市番号は入力と同じ 1始まり、bit位置は 0始まり とする。固定端点 i (1≤i≤k)i\ (1\leq i\leq k) に対応するbitは i−1i-1 である。例えば K=3K=3 なら、都市1はbit 0(mask 1)、都市2はbit 1(mask 2)、両方を含む集合はmask 3(二進表記 11)になる。全固定端点を表すmaskを full = (1 << k) - 1 とする。

非空mask ss と都市 v (1≤v≤N)v\ (1\leq v\leq N) に対し、dp[s][v]dp[s][v] を「ss に含まれる固定端点と vv をすべて含む木の最小費用」と定める。vv をこの木の根と呼ぶが、葉である必要はなく、固定端点と一致してもよい。また、ss に含まれない端点を中継に使ってもよい。追加都市をbitに入れず、この根として残すことが、全都市の答えを共有する鍵になる。

初めはすべて ∞\infty とし、各固定端点 ii について dp[1 << (i - 1)][i] = 0 と置く。端点一つと根が同じなら、辺を使わない木でよいからである。maskの配列長は 2k2^k、使用するmaskは1から full までで、mask 0は使わない。K=2K=2 でも都市1の初期値は dp[1][1] = 0 となり、長さ2の配列に収まる。

各maskを整数として小さい順に、次の二段階で確定させる。

  1. 同じ根で集合を合成する。 ss の非空な真部分集合を表すmask tt をすべて選び、各根 vv で次の更新を行う。

    dp[s][v]←min⁡(dp[s][v], dp[t][v]+dp[s⊕t][v])dp[s][v]\leftarrow\min\bigl(dp[s][v],\ dp[t][v]+dp[s\mathbin{\oplus}t][v]\bigr)

    ⊕\oplus はbitごとの排他的論理和で、ここでは ss から tt のbitを除いた残りを表す。二つの木が vv を共有すれば、合併して両方の端点をつなげる。どちらのmaskも正で ss より小さいため、その最短路計算まで完了した値を読める。

  2. 同じ集合のまま根を移す。 合成直後の有限な dp[s][u]dp[s][u] を、全都市 uu からの初期距離として優先度付きキューへ入れ、多始点Dijkstra法を行う。辺 u ⁣− ⁣vu\! -\! v の重みが ww なら、次の更新で根を移せる。

    dp[s][v]←min⁡(dp[s][v], dp[s][u]+w)dp[s][v]\leftarrow\min\bigl(dp[s][v],\ dp[s][u]+w\bigr)

    初期距離はすべて0ではなく、各都市を根にするまでの費用である。この処理は、任意の都市で得た合成結果へ経路を付け足す全候補を求める「最短路閉包」に当たる。同じmask内には辺に沿った循環依存があるため、頂点番号順の一巡では足りない。

端点一つだけのmask(singleton)でも、第二段階を省略しない。この場合は合成する真部分集合がないが、初期値0の端点からの最短距離を全都市へ伝える必要がある。したがって K=2K=2 の全体は、都市1を始点とする通常の最短路計算になる。

公式sample 1は K=3K=3 なので、固定端点は都市1、2である。都市を根にしたsingletonの距離と、mask 3の合成直後・最短路閉包後の値を並べると次のようになる。最後の列が dp[3][v]dp[3][v] に当たる。

根 vvdp[1][v]dp[1][v]dp[2][v]dp[2][v]合成後閉包後
10333
23033
31233
43696

都市3では、都市1からの費用1と都市2からの費用2を合成して3になる。都市4で二つの最短路をそのまま合成すると9だが、都市1を根とする費用3の木に、都市1と4を結ぶ重み3の辺を足せば6になる。この改善を第二段階が伝える。最後に full は3なので、追加都市 v=3,4v=3,4 について dp[3][3]=3dp[3][3]=3、dp[3][4]=6dp[3][4]=6 を読み出す。

一般にも、閉包まで済んだ dp[full][v] が追加都市 vv の答えである。v=K,K+1,…,Nv=K,K+1,\ldots,N の順に、N−K+1N-K+1 行で出力する。

典型の発動条件

Dreyfus-Wagner型Steiner DP

発動条件は、非負重みの無向グラフで、少数の端点を中継点も使って最小費用でつなぐこと。グラフ全体の部分集合ではなく、端点の部分集合だけを指数状態にする。木の分岐を同一点での集合合成、分岐間の経路を根の移動として分ける。

multi-source Dijkstra閉包

発動条件は、集合を固定したまま非負重みの辺に沿って移動でき、各頂点に既知の初期費用があること。初期費用ごとキューに入れれば、「どこから移動を始めるか」も含めて最小化できる。すべての初期距離を0にする通常の多始点探索との違いに注意する。

問題固有の要素

問いごとに変わるのは最後の主要都市だけで、固定端点は共通している。追加都市を集合のbitへ入れ直す代わりに、DPが元から持つ根の位置として読むことで、全都市の答えを一つの表から得られる。多数の問いが小さな必須集合を共有するとき、変わる一点を接続点の軸へ移せないか考える。

正当性

まず、遷移が真の最適値より小さい費用を作らないことを確認する。二つの部分木の合併も、木に経路を付け足したものも、必要な端点と根をつなぐ。辺が重複して二重計上されても、実際の合併の費用は候補値以下であり、非負重みなので閉路を取り除いて木にできる。したがって、候補値以下の費用で有効な木を作れ、重複は過小評価の原因にならない。

逆に、任意の非空集合の最適木を遷移で捉えられることを、端点数について帰納的に示す。端点が一つなら、その端点と根を結ぶ最短路が最適であり、初期値0からのDijkstra法が求める。

端点が二つ以上の場合、最適木から、今回の集合に含まれる端点でも根でもない葉を繰り返し取り除く。根 vv から一本道をたどり、初めて集合内の端点に着くか、端点へ向かう枝が二つ以上に分かれる頂点 xx を選ぶ。根で既にこの条件を満たすなら x=vx=v とする。xx が端点なら、その端点一つと残りに集合を分ける。xx が端点でなければ、xx から先の枝を二組に分け、各組にある端点で集合を分ける。不要な葉を除いてあるので、どちらの組にも端点がある。

この分け方では、二つの部分木は xx で合流し、根 vv までの経路とは辺を共有しない。片方が端点 xx 一つの場合、その部分木の費用は0でよい。帰納法の仮定で各部分木の費用以下の値が既に求まり、xx での合成と xx から vv への最短路閉包が、元の最適木の費用以下の候補を作る。根そのものが端点でも、x=vx=v としてこの分解ができる。

過小評価しないことと合わせて、各maskの閉包後の値は定義した最適費用に一致する。よって、全固定端点のmaskを取り、根を追加都市にした値が求める答えである。

実装上の注意

  • 都市番号は1から NN、maskのbitは0から k−1k-1。都市用配列を長さ N+1N+1、mask用配列を長さ 2k2^k とすれば、本文の添字をそのまま使える。
  • 非空な真部分集合は、擬似コードとして t = (s - 1) & s から始め、t > 0 の間 t = (t - 1) & s で列挙する。mask 0と ss 自身を読まない。補集合 s ^ t も必ず非空で ss より小さい。二つの組を入れ替えた合成は重複しても正しさを保つ。
  • 合成では両方の値が有限のときだけ加算する。Dijkstra法のキューにも有限値だけを入れ、取り出した距離が現在値と違えば古い候補として捨てる。
  • 有限な最適費用は (N−1)×109≤3.999×1012(N-1)\times 10^9\leq 3.999\times 10^{12} 以下なので、費用とその和には64 bit整数を使う。例えば無限大の番兵値を INF = 1LL << 60 とし、無限大との加算を避ける。
  • 道路は双方向に登録する。同じ都市対に複数の道路があっても、それぞれを隣接リストへ入れてよい。

復習の核

  • 端点が少ない最小接続問題では、端点の部分集合と接続点を状態にし、木の合成と経路の延長に分ける。
  • 合成元の小さい集合は最短路閉包まで済ませておく。端点一つの集合にも、他の根への距離を伝える処理が必要である。
  • 多数の問いで変わる一点を、集合のbitへ追加せず根として読めないか考える。
  • 都市番号とbit位置は別の添字である。K=3K=3 で「都市1・2がbit 0・1、全体がmask 3」と確認する。

計算量と制約

時間

全maskにわたる部分集合の分割は、各端点を「左側・右側・今回の集合外」の三通りに振り分けるので O(3k)O(3^k) 組、各根で合成して O(3kN)O(3^kN)。二分heapへ改善候補を追加するDijkstra法は、各maskで O((N+M)log⁡(N+M))O((N+M)\log(N+M)) かかる。入力・初期化・出力を含む全体は

O(3kN+2k(N+M)log⁡(N+M)+N)O\bigl(3^kN+2^k(N+M)\log(N+M)+N\bigr)

となる。出力は N−K+1N-K+1 個である。

空間

DP表に O(2kN)O(2^kN)、隣接リストと一回分の優先度付きキューに O(N+M)O(N+M) を使い、全体は O(2kN+N+M)O(2^kN+N+M)。

制約との対応

公式制約は 2≤N≤40002\leq N\leq 4000、N−1≤M≤8000N-1\leq M\leq 8000、2≤K≤min⁡(N,10)2\leq K\leq\min(N,10)。道路の端点は 1≤Ai<Bi≤N1\leq A_i<B_i\leq N、費用は 1≤Ci≤1091\leq C_i\leq 10^9 で、グラフは連結、入力はすべて整数である。実行時間制限は5秒、メモリ制限は1024 MiB。

k=K−1≤9k=K-1\leq 9 なのでmask数は最大512、DP表は都市用の余白を含めても約205万要素で、64 bit整数なら約16.4 MBになる。指数部分を全都市ではなく固定端点だけにかけられる点が制約に対応する。非負重みだからDijkstra法を使え、連結なので出力する答えはすべて有限である。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Last Major City の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 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 3

    学習の位置

    体系上の位置: Steiner tree subset DP

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

    先に読む単元:

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題