d_tutuz https://blog.hatena.ne.jp/d_tutuz/ 数学/競プロメモ https://tutuz.hateblo.jp/ 問題 https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_e 考え方 連結成分について連結した状態から、除々に辺を切断して非連結にしていきたい。UnionFindは頂点の連結しかできないがどうするか？という問題である。 逆に非連結の状態から除々に辺で連結されていき、連結成分の頂点の重みの合計が辺の重み以上になっている場合には、連結成分で使われている辺はすべて削除不要な辺である。このようにして小さい重みの辺から除々に考えていくと自然に解を求めることができる。 Submission #4179875 - 全国統一プログ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftutuz.hateblo.jp%2Fentry%2F2019%2F02%2F05%2F213617" title="全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019：E - Weights on Vertices and Edges - 数学/競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2019-02-05 21:36:17 rich https://tutuz.hateblo.jp/entry/2019/02/05/213617 1.0 100%