足跡-sokuseki-

りかの日進月歩の記録

ABC065/ARC076 D Built?

競技プログラミング AtCoder

問題概要

$N$ 個の街があり、 $i$ 番目の街は座標 $( x_i , y_i )$ にある。
座標 $(a, b)$ にある街と座標 $(c, d)$ にある街の間に道をつくるのに、コストが $min(|a-c|, |b-d|)$ 円かかる。
任意の2つの街の間を道を通って行き来できるようにするための最低コストを求めよ。

制約
$1 \le N \le 10^5$
$0 \le x_i, y_i \le 10^9$

解法

3つの街が $(a, b), (c, d), (e, f)$ にあるとする。
$a < c < e$ かつ $b < d < f$ のとき、 $(a, b)$ と $(c, d)$ の間、 $(c, d)$ と $(e, f)$ の間の2つの道を作るならば、 $( a, b)$ と $(e, f)$ の間に道を作る必要はない。
このことから、 $x$ 座標または $y$ 座標が最も近い街同士だけの辺を考えれば良いことがわかる。

また、任意の2つの街を行き来できるというのは、街を頂点、道を辺としたグラフが連結であり、連結グラフの辺のコストを最小化するのは、グラフの最小全域木を構成するということになる。

よって解法は

$x$ 座標でソートして隣り合う街に辺をはる
$y$ 座標でソートして隣り合う街に辺をはる
最小全域木を求め、コストを出力する

辺は高々 $2(N-1)$ 本しかないので、計算量は $O(NlogN)$ になる。

Submission #1994769 - AtCoder Regular Contest 076