グラフ-最小全域木（MST）-クラスカル法
最小全域木（MST）については以下： 最小全域木（MST - Minimum Spanning Tree） - 競プロはじめましたUnionFindについては以下： UnionFind木 - 競プロはじめました 考え方 回答例 考え方クラスカル法を使う．以下のようにすれば良い．一度のクラスカル法で…
用語 アルゴリズム 例題 用語用語を整理しておきます（蟻本p. 99-）： 全域木：無向グラフの部分グラフで，任意の2頂点が連結である木． 最小全域木：辺のコストの和が最小の全域木． アルゴリズム プリム法：木$T$に，木$T$の頂点と木$T$に含まれない頂点を…
クラスカル法クラスカル法．コストの小さい順に辺を見ていき，閉路・二重辺でなければ追加する．UnionFindを使う．バラバラの状態からはじめ，辺の頂点が同じグループに属していないなら追加すれば良い．UnionFindコストが負の辺は取り除く意味がない（すべ…
