search

Harui-i / library

library for competitive programming
https://harui-i.github.io/library/
0 stars 0 forks source link

ポテンシャルつきUnionFind #16

Closed Harui-i closed 4 months ago

Harui-i commented 4 months ago

Verify用リンク: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_B

ei13333: https://ei1333.github.io/library/structure/union-find/weighted-union-find.hpp

drkenによる解説:[https://qiita.com/drken/items/cce6fc5c579051e64fab] (https://qiita.com/drken/items/cce6fc5c579051e64fab) → 言われてみればポテンシャルつきUnionFindって差分制約だから、牛ゲーとか最小費用流とかとの関連性があるのも納得だ。深い気がするね。

Harui-i commented 4 months ago

たぶん これ ABC328-f がポテンシャルつきUnionFindで解けるんだけど、解けなかったらちょっと困っちゃうかも

Harui-i commented 4 months ago

https://noshi91.hatenablog.com/entry/2018/05/30/191943

これに言及があるな

Harui-i commented 4 months ago

https://sigma425.hatenablog.com/entry/2015/12/07/185047 path上のminみたいな、逆元が無いものもlogで解けるらしい

Harui-i commented 4 months ago

ACLとインターフェイス揃えたいね

Harui-i commented 4 months ago

やりました。