概要
すこし計算量の良い別解だと思います。他の提出と実行速度を見比べても、パフォーマンスは良さそうです。
公式解説と同様、グラフの頂点に赤青の 2 色のどちらかを割り当てる問題に読み替えておきます。
解法
ひとつずつ頂点・辺を追加していく DP を考えます。頂点を $0, 1, 2, \ldots$ 順に追加していきます。
頂点 $n$ までを考えているとして、
- 各部分集合 $S\subset \{0,1,\ldots,n\}$ に対して、赤く塗った頂点集合が $S$ である場合についての
- これまで考慮した辺に関する合計スコアの最小値
- 最小値を達成する方法の総数
を管理する dp を考えます。このままでは、全探索しているのと全く違いがありません。もう少し状態をまとめます。
ある頂点 $v$ に接続する辺のスコアの情報を計算してしまった時点で頂点 $v$ に塗った色は忘れてよいことに注目します。頂点や辺を BFS 順に追加していきます。例えば次の図で以下の手順で計算します。
- 頂点 $0$ の塗り方を dp の状態に追加する。dp の状態数が $2^1$ 通りになる。
- 頂点 $1$ の塗り方を dp の状態に追加する。dp の状態数が $2^2$ 通りになる。
- 各状態に、辺 $01$ のスコアを加算する。
- 頂点 $2$ の塗り方を dp の状態に追加する。dp の状態数が $2^3$ 通りになる。
- 各状態に、辺 $02$ のスコアを加算する。
- 頂点 $3$ の塗り方を dp の状態に追加する。dp の状態数が $2^4$ 通りになる。
- 各状態に、辺 $02$ のスコアを加算する。
- 頂点 $0$ の塗り方の情報を、dp の状態から捨てる。$2$ 通りずつの状態をまとめて、 dp の状態数が $2^3$ 通りになる
- 各状態に、辺 $12$ のスコアを加算する。
- 頂点 $1$ の塗り方の情報を、dp の状態から捨てる。$2$ 通りずつの状態をまとめて、 dp の状態数が $2^2$ 通りになる
- 頂点 $4$ の塗り方を dp の状態に追加する。dp の状態数が $2^3$ 通りになる。
- $\vdots$
各頂点の近傍が小さいことを使って、この解法の計算量を評価しましょう。各頂点の次数が $4$ 以下です。特に BFS の始点を除けば、「新しい頂点を $3$ つ以下追加 → もとの頂点の情報を忘れてよい」となります。グラフ全体の頂点数を $N$ とすれば、各時点で管理すべき dp の状態数は最大でも $2/3N + O(1)$ 程度にしかなりません。
頂点の追加削除は $O(N)$ 回。辺の個数も全体で $\frac12\sum_{v}\deg(v) \leq 2N$ ですから、
- 空間計算量 $O(2^{2/3N})$
- 時間計算量 $O(N\cdot 2^{2/3N})$
で解くことが可能です。
