競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2382 King Slime

問題文

King Slime | Aizu Online Judge
日本語訳は略

解法

M個の頂点があったときに,それを1点に集合させるまでに必要な移動回数の下界はM-1回でとなる.
これは,各頂点からの移動を辺で表せば木となることから明らかである.

というわけで,木を構成する方法について考える.
同じx座標またはy座標を持っている頂点同士は辺を張ることができ,グラフを構築するといくつかの連結成分に分かれる.
連結成分内では木を構成することができるので一点に集める.

異なる連結成分同士は壁を使って壁沿いに一列に並べてからくっつけるしかないので,適当にやる.
ここで,連結成分内に壁沿いの頂点を持っている連結成分があるとその壁に全部寄せることで回数が少なくできたりするので処理に工夫が必要となる.

計算量は座圧が必要なのでO(NlogN)