AOJ 2224 Save your cat

Jul 3, 2014  

フェンスを辺と考え、閉路をなくせばよいので、
閉路をなくす → 全域木の辺の数を最小にする
壊す長さを最小に → 長い辺から使っていく
と考えると最小全域木と同じような解き方で解けます。

UnionFind木を使ったクラスカル法で解く場合。
fenceをcostの大きさで降順にソートして、
使わなかったfenceのcostの和を出力します。

プリム法で解く場合。
プリム法は最小全域”木”をつくるので、森をつくるため、
使われていない頂点に対して何度かプリム法で木を作ります。
(森に対してプリム法を使う方法これしかおもいつかない……)
あと、この実装方法だと同じ辺を何度もみることがあるので
クラスカル法の時のように素直にsumを出力できません。

このエントリーをはてなブックマークに追加