グラフ-最小全域木（MST）
最小全域木（MST）については以下： 最小全域木（MST - Minimum Spanning Tree） - 競プロはじめましたUnionFindについては以下： UnionFind木 - 競プロはじめました 考え方 回答例 考え方クラスカル法を使う．以下のようにすれば良い．一度のクラスカル法で…
用語 アルゴリズム 例題 用語用語を整理しておきます（蟻本p. 99-）： 全域木：無向グラフの部分グラフで，任意の2頂点が連結である木． 最小全域木：辺のコストの和が最小の全域木． アルゴリズム プリム法：木$T$に，木$T$の頂点と木$T$に含まれない頂点を…
クラスカル法クラスカル法．コストの小さい順に辺を見ていき，閉路・二重辺でなければ追加する．UnionFindを使う．バラバラの状態からはじめ，辺の頂点が同じグループに属していないなら追加すれば良い．UnionFindコストが負の辺は取り除く意味がない（すべ…
解答の補足事項のみ書いておく．以下では，$l, m,n\in \mathbb{Z}$とする．はじめに$A_{i_{1}}$を選び，辺を張れるだけ張ったすると，$x$と同じ連結成分にできる頂点は\begin{aligned} & x + l A_{i_{1}} \pmod N \\ & \Leftrightarrow x + l A_{i_{1}} + m …
