7K12 blog

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

ABC065 D - Built?

f:id:tkr987:20210515032612p:plain

https://atcoder.jp/contests/abc065/submissions/22580754

  • 本当に N^2本の辺を全て試す必要があるか疑うこと

f:id:tkr987:20210515174427p:plain

最小全域木なのでクラスカル法ライブラリを貼りたいが、設問そのままグラフを処理しようとすると O(N^2 \log N)で間に合わない。街1と繋がるべき街は2と3、街4と繋がるべき街は5だが、更に各々の連結成分同士を繋げる(xまたはyの絶対値最小の差なので街3と街5)ことで最小全域木が出来上がる。したがって、 N^2本の辺は無駄が多くて実際にはxまたはyの絶対値最小の街同士だけで辺を貼ったグラフで十分。このグラフに対してクラスカル法を実行すれば O(N \log N)で処理できる。