NIKKEI Programming Contest 2019 E - Weights on Vertices and Edges
日経のコンテスト出ましたがこれが通せなかったため解法をマスターしておく。この手の問題は得意だったはずなのに通せなかったのは少し反省。
「辺をいくつか除いたときの連結成分ごとのほにゃらら」は逆から考えてUnion Findで処理する。ここまではすぐ発想できた。このとき、この考えで辺の重みを小さい方から付け加えていったときに、トータルの連結成分の頂点の重みの総和はUnion Findで計算できる。これを計算した直後に、今見ている辺の重みと比較することで最終的にその辺が使われるかどうかが判定できる。更にそのへんはその時点での各連結成分の中で最大の重みを持つ辺になっている。
そこで上記の処理が全て終わったら今度は上記の結果必ず使われる辺のリストで、辺の重みの大きい方から、その辺の重み以下の辺からなる連結成分をdfsですべて塗りつぶしていく。計算量を落とすためにすでに通った辺は無視するものとする。このとき、辺の重みを小さい方からやってしまうと、小さい重みを持つ辺でブロックされてしまうエリアができてしまい、その後から大きい辺でdfs しようとしても「すでに通った辺は無視」というロジックによって塗りつぶされないエリアができてしまう。
計算量は辺のソートでO(m log(m))
