uva 10034 Freckles

uva 10034 Freckles を解きました。

記事書いてもらったので感謝しつつ最小全域木を求める2つのアルゴリズム : R SATO Weblog などを参考に、 Union-Find を利用して最小全域木を作る kruskal のアルゴリズムを書いてみました。 A 問題ということもあり、わりとサクッと行けました。

この問題は、平面座標が複数与えられたときに全ての点を最も短く繋ぐような辺の張り方（最小全域木）を求めてその辺の長さの総和を出すという話。具体的には次のように書いてみた。

1. 2 点間の距離を全ての組合せについて計算して、その値とどの 2 点間の距離かという情報を pair にして queue（実際は priority_queue）に push する。
2. 求める距離 d を 0 に初期化し、queue が空になるまで次のことを繰り返す。
   1. queue から pop して、
   2. その 2 点が同じ集合に無いなら、集合に入れて、その距離を d に加える。

3. d を出力

priority_queue はそのまま使うと最大値が一番最初に来るので、最も短い辺から選ぶには priority_queue<diipair, vector<diipair>, greater<diipair> > dque; みたいに三つ目を greater 関数オブジェクトにする必要があるとか、上記 2 の中でグラフが連結になったらその時点で抜けると早そうとか。今更だけど、そもそも priority_queue じゃなくて vector に入れて最後に sort すれば用は足りるよな…とか思った。次はそれで書こうと思います。

Union-Find のところは（てけとーに）クラス化してるので、実質的に書いたのは 70 行くらいか。 STL ばんざいだよお。

kruskal はもっと練習しないと…。 prim も早いとこ書かないとなー。