クラスカル法
クラスカル法.コストの小さい順に辺を見ていき,閉路・二重辺でなければ追加する.UnionFindを使う.バラバラの状態からはじめ,辺の頂点が同じグループに属していないなら追加すれば良い.UnionFind
コストが負の辺は取り除く意味がない(すべてつなげたままで良い).- コスト(報酬)の小さい順に辺をソートする.
- コストの小さい順に辺を見ていき
- 報酬がゼロ以下ならつなげる.
- 報酬が正のとき,①つながっていないならつなげる,②既につながっているなら,見ている辺は取り除いて良い辺なので,報酬を答えに加算する.
【参考】
- Submission #25761257 - AtCoder Beginner Contest 218
- Submission #25762914 - AtCoder Beginner Contest 218
アライグマ「E問題は最小全域木なのだ! 「辺を消しても連結のままか?」っていう問題はだいたい難しいから、逆から考えて「辺を増やして連結にできるか?」ってやるのが基本なのだ!」https://t.co/i2lLSVZWbI
— 競技プログラミングをするフレンズ (@kyopro_friends) September 11, 2021