finals - 本選会場 (Finals) Editorial by Mitsubachi

$K=1$ のとき、これは最小全域木 $T$ を求める問題になります。すなわち、答えは最小全域木 $T$ の辺のコストの合計となります。

証明

初めに、 $T$ の辺のコストの合計で選手を集められることを示します。これは以下のようにすることで可能です。

  • 都市を頂点、道路を辺と見立てる。ここで、選んだ頂点を根とする根付き木を考える。
  • 各頂点 $i$ について、その頂点の子である頂点 $j$ に $j$ と $j$ の子孫に最初いた選手が全員いるとき、子にいる選手を全員 $i$ に集める。その後、 $i$ にいる選手全員を $i$ の親に移動させる。

また、最適な方法において移動に使った辺からなるグラフ $G$ が全域木であることの証明は以下の通りです。

選手を集める過程で使った辺からなるグラフ $G$ を考える。これは明らかに連結であるため、これが木でない場合閉路が必ず存在する。
この過程においてかかったコストは $G$ の全辺にかかるコストの合計以上であるが、 $G$ の全域木を選び、上のようにすることでより最適であるような集め方が可能。このような全域木は、閉路のうち $1$ 辺を取り除くことで可能である。
これより $G$ が木でない場合最適でないことがいえるので、対偶より最適な方法において、使用した辺からなるグラフは木となることが示せる。
また $G$ の含む辺は全て移動に使われたので、コストは最低でも $T$ の辺のコストの合計となります。

以上より、最小となるコストが \(T\) の辺のコストの合計であることが示されました。

最小全域木はクラスカル法やプリム法などで求めることができます。さて、 \(2 < K\) の場合を考えましょう。上のように考えることで、\(K\) 個の木からなる最小全域森を求めればよいことになり、これはクラスカル法の要領で以下のようにすることで達成できます。なお、森の場合でも最適であることはマトロイド性を用いることで証明可能です。

  • 道路を $C_i$ の昇順にソートする。変数 $ans=0,size=N$ を定義し、 $N$ 頂点 $0$ 辺のグラフを考える。
  • $1$ 番目の道路から順に操作を行う。$i$ 番目の道路では以下のようにする。
    • $A_i$ と $B_i$ が非連結なら $A_i$ と $B_i$ を結ぶ辺を追加し、 $ans$ に $C_i$ を加算、 $size$ から $1$ を引く。

この操作にて \(size=K\) となったとき、その時点での \(ans\) が答えとなります。Union-findなどで実装することができ、計算量は \(O(N \alpha(N)+M \log M)\) となります。

posted:
last update: