7K12 blog

猫でも分かるアルゴリズム解説

2010年 日本情報オリンピック春合宿 - Finals

f:id:tkr987:20200723001928p:plain

https://atcoder.jp/contests/joisc2010/submissions/15253528

  • 最小全域木のうち最長の辺をK-1個だけ取り除いてK個のグラフに分ける
  • K個の開催都市を何処にするかは無関係(一度に複数人通行させれば料金一律なので
  • 辺をK-1個だけ取り除くことでグラフをK個に分割できる

f:id:tkr987:20200723003916p:plain

開催都市が1個なら簡単で最小全域木を構築するだけになる。開催都市がK個のときも人々が最善の移動をしたと仮定すれば、(最小全域木上にあれば)開催都市が何処でも最小料金合計は変化しない。

ただし、開催都市がK個のときはグラフをK個に分割することで、辺の長さを減らすことが出来る。グラフをK個に分割するとき、辺をK-1個だけ取り除くことが出来る。したがって、人々の移動距離を最小にするため、最小全域木から貪欲にK-1個だけ辺を取り除いたグラフが答えになる。