Potentialized UnionFind (重み付き UnionFind)
(unionfind/potentialized_unionfind.hpp)
2個の要素間の重みづけが可能な UnionFind.
使用方法
ポテンシャルが(ふつうの)整数の場合.
PotentializedUnionFind<int> uf(N);
uf.unite(s, t, diff); // f[t] = f[s] + diff を要請.これまでの要請と矛盾すれば false を返す.
auto x = uf.diff(s, t); // f[t] - f[s] (として考えられる値の一つ)を出力.
ポテンシャルが $\mathbb{F}_{2}$ 上のベクトルの場合.
PotentializedUnionFind<Nimber> uf(N);
問題例
Verified with
Code
Back to top page