ABC218E - Destruction

クラスカル法

クラスカル法.コストの小さい順に辺を見ていき,閉路・二重辺でなければ追加する.UnionFindを使う.バラバラの状態からはじめ,辺の頂点が同じグループに属していないなら追加すれば良い.

UnionFind

コストが負の辺は取り除く意味がない(すべてつなげたままで良い).
  1. コスト(報酬)の小さい順に辺をソートする.
  2. コストの小さい順に辺を見ていき
    • 報酬がゼロ以下ならつなげる.
    • 報酬が正のとき,①つながっていないならつなげる,②既につながっているなら,見ている辺は取り除いて良い辺なので,報酬を答えに加算する.

【参考】