https://atcoder.jp/contests/joisc2010/submissions/15253528
- 最小全域木のうち最長の辺をK-1個だけ取り除いてK個のグラフに分ける
- K個の開催都市を何処にするかは無関係（一度に複数人通行させれば料金一律なので）
- 辺をK-1個だけ取り除くことでグラフをK個に分割できる
開催都市が1個なら簡単で最小全域木を構築するだけになる。開催都市がK個のときも人々が最善の移動をしたと仮定すれば、（最小全域木上にあれば）開催都市が何処でも最小料金合計は変化しない。
ただし、開催都市がK個のときはグラフをK個に分割することで、辺の長さを減らすことが出来る。グラフをK個に分割するとき、辺をK-1個だけ取り除くことが出来る。したがって、人々の移動距離を最小にするため、最小全域木から貪欲にK-1個だけ辺を取り除いたグラフが答えになる。
