全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019：E - Weights on Vertices and Edges
問題
https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_e
考え方
連結成分について連結した状態から、除々に辺を切断して非連結にしていきたい。UnionFindは頂点の連結しかできないがどうするか？という問題である。
逆に非連結の状態から除々に辺で連結されていき、連結成分の頂点の重みの合計が辺の重み以上になっている場合には、連結成分で使われている辺はすべて削除不要な辺である。このようにして小さい重みの辺から除々に考えていくと自然に解を求めることができる。
Submission #4179875 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019
どこに着目して考察するべきだったか
操作の逆を考えて、徐々に辺で連結させていく操作を考えると自然に解ける
何がバグっていたか
得た知見(典型ポイント)
- 操作の逆を考える(連結から非連結にする)
