Finals(本選会場) - joi2010-day3 解説

筆者: qnighy

無向グラフ上で輸送コストが最小となるように会場と輸送路を選択する問題である。

K=1, O(N^2)解法

(思いつかなかったので省略)

O(N^2)解法

(思いつかなかったので省略)

K=1, O(NlogN)解法

少し調べてみると、開催する会場がどこにあるかは実はあまり意味がないことがわかる。

したがって、輸送路をどちらの方向に使うかも実は意味をもたない。単に、全部の都市を繋ぐのに必要な最小コストの辺集合を考えればよいことがわかる。

これはまさしく世に言うところの「最小全域木」であり、有名アルゴリズムであるKruskalまたはPrimによって解くことができる。

O(NlogN)解法

Kが1でない場合も、実は同様の方法で解くことができる。ここではKruskalを用いるほうが簡単である。

Kruskalはある種の貪欲法であり、その途中経過は、まさしく会場がK個あるときの最適な解である。そのため、Kruskalを途中で止めたときのコストがそのまま答えとなる。

もしPrimで解きたい場合は、いったんPrimを適用した後、使用した辺のなかでコストの大きいものから切断していけばよい。