考察
削除した辺の C_i を得る問題は、全辺をいったん削除した総額から、連結にするため戻す辺の C_i を差し引く問題と見られる。したがって、残す辺の重み和を小さくしたい。C_i<0 の辺は削除すると罰金になる一方、余分に残しても連結性を損なわないので、全域木に選ばれなかった負辺も削除しない方がよい。Kruskal 法で両端が既に同じ成分にある辺は連結維持には不要であり、その重みが正のときだけ削除する価値がある。
採用する候補: 辺を C_i の昇順に Kruskal 法で処理し、異なる連結成分を結ぶ辺は残し、既に連結な両端を持つ正辺だけを削除報酬へ加える。
連結に必要な辺を最小全域木と同じ交換則で選びながら、MST 外の負辺を残すという例外も符号判定で正しく扱える。
棄却する候補: 正の大きい辺から実際に削除し、そのたびにグラフが連結か判定する。
貪欲な選択自体は成立するが、辺削除を伴う動的連結性を各回高速に判定する実装が必要になり、単純な BFS/DFS の反復では制約に収まらない。
全辺を重み昇順に並べて DSU で処理する。成分が異なれば unite して辺を残し、同じ成分なら C_i>0 の場合だけ答えに C_i を加え、C_i≤0 なら報酬を悪化させないため残す。
典型の発動条件
削除利益から残存コストへの反転
発動条件: 要素を削る利益を最大化しつつ、残した集合が連結などの被覆条件を満たすとき。
全削除時の利益を基準に、条件を満たすため戻す要素のコスト最小化として考える。
Kruskal 法と DSU
発動条件: 無向グラフを連結に保つため必要な辺を、辺重みの和を小さく選びたいとき。
軽い辺から成分間だけを採用し、cycle を作る正辺を不要と判定する。
問題固有の要素
最小全域木だけを残すのではなく、MST に入らない負辺も残す必要がある。負辺は「余分な辺」でも削除報酬が負だからである。
別の問題へ持ち帰る視点: 最適な基底を使う変形では、基底外の要素を自由に残せるか、その符号が目的値を改善するかを別に確認する。
正当性
負辺削除は報酬を減らすため残すのが最適。非正辺を全て残して縮約した後、正辺で連結性を保つ最小cost forestをKruskal交換法で選ぶ。それ以外の正辺を削る報酬が最大になる。
実装上の注意
- 自己ループや多重辺も DSU の「既に同成分」で自然に処理できる。C_i=0 は加算してもしなくても値は同じだが、答えは 64 bit 整数で保持する。
復習の核
- 負辺だけで cycle ができる小例を作り、「MST にないから削除」が誤りになることを先に確認してから Kruskal の分岐を復元する。
計算量と制約
時間
N頂点M辺。sortとKruskal O(M log M+Mα(N))。
空間
辺とDSU O(N+M)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2\times 10^5; N-1 \leq M \leq 2\times 10^5; 1 \leq A_i,B_i \leq N; -10^9 \leq C_i \leq 10^9; The given graph is connected.; All values in input are integers.
出典