ABC065 D - Built?
解法
考察でごり押したら最小全域木とかいうやつを使っていたみたいです。
初期状態だと辺の可能性が約本あるので、これだと何をするにも不便です。
ですが、実は本程度まで減らすことができます。
個の座標をxについてソートした場合の隣り合った頂点同士の辺のみが最終的に使用されるからです。yについても同様です。
隣り合っていない頂点a,bについては、間にいくつかの頂点があり、それを経由することで結局和がa,bの辺のコスト以下になるような辺の組み合わせで移動できるからです。
ということは、結局a,bの辺はいらないことになります(コストが同じだった場合でも、いくつかの頂点を経由できる時点で、そちらの方が優秀な辺の選び方になります)。
ということで、本程度の辺を抽出できました。
あとは、この中から最終的に本の辺を選び、連結かつ辺のコストの総和が最小になるようにしたいです。
ここで、最小全域木の考え方そのものになります。
辺を、コストの少ない順にソートして、順番に辺を取り出していき(これは優先度付きキューを使えば実装できます)、取り出した辺が既に連結でなければその辺を採用、連結であれば不採用ということを繰り返していけば良いです。連結かどうかは、UnionFind木を利用していけばよく、採用されたらその2つの辺をマージします。
そして、採用した辺のコストの和が答えになります。
