ABC218 E「Destruction」解説｜Kruskalで辺削除報酬を最大化

ABC218 Eは削除報酬を最大化する問題

ABC218 E「Destruction」は、元の無向グラフが連結という条件の下で辺を削除し、削除した辺のコスト合計を最大化する問題です。コスト C_i が0以上の辺を削除すると C_i の報酬を得て、C_i < 0 の辺を削除すると |C_i| の罰金が発生します。入力条件と公式サンプルはAtCoderの問題文で確認できます。

公式解説は、削除後に残す辺の接続コストを最小にする問題へ言い換え、最小全域木（MST）に還元しています。MSTは計算に使う基準であり、答えとして木の辺を出力する問題ではありません。求めるのは、連結性を保ちながら削除できる辺の最大報酬です（ABC218 Eの公式解説）。

削除報酬の最大化がMSTへつながる理由

全辺のコスト合計は固定です。したがって、削除した辺のコスト合計を大きくすることは、残した辺のコスト合計を小さくすることと同じです。残した辺は全頂点をつなぐ必要があるため、接続に必要な最小コストの骨格をMSTで選べます。

負の辺は削除すると罰金になるので、MSTの辺に選ばれなくても残します。負辺を追加で残しても連結性は壊れず、削除による罰金も避けられます。コスト0の辺は残しても削除しても報酬に影響しません。そこで、Kruskalが接続用に選ばなかった辺のうち、正の辺だけを削除して報酬へ加えます。

KruskalとUnion-Findで連結成分を追う

Kruskalは辺をコストの小さい順に調べます。Union-Findは、これまでに接続した頂点のグループ（連結成分）を管理します。辺の両端の代表元が異なれば、その辺で二つの成分をつなぎます。同じなら、すでに選んだ辺で両端がつながっているため、その辺を接続用の木へ加える必要はありません。正の辺なら削除報酬へ加算し、負の辺は削除しないままにします。

公式サンプル1では、最初は頂点1、2、3、4がそれぞれ別の成分です。辺をコスト順に処理すると、最初の3辺で4頂点がつながり、その後の2辺はすでに同じ成分を結びます。

接続に必要な3辺を残せば、2本のコスト2の辺を外しても連結です。報酬は 2 + 2 = 4 になります。

入力から答えまでのPython参考コード

入力の頂点番号は1始まりなので、読み込んだ後に0始まりへ変換します。findは代表元を調べ、異なる成分を結ぶときはサイズの大きい側へ併合します。

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
edges.sort(key=lambda edge: edge[2])

parent = list(range(N))
size = [1] * N

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

answer = 0
for a, b, cost in edges:
    a -= 1
    b -= 1
    root_a, root_b = find(a), find(b)
    if root_a == root_b:
        if cost > 0:
            answer += cost
    else:
        if size[root_a] < size[root_b]:
            root_a, root_b = root_b, root_a
        parent[root_b] = root_a
        size[root_a] += size[root_b]

print(answer)

正しさと計算量

Kruskalが異なる成分を結ぶ辺だけを選ぶため、選ばれた辺に閉路はできません。入力グラフは連結なので、処理後には全頂点を結ぶ最小コストの木ができます。負の辺は、その木の外にあるものも残すので、木は連結に必要な辺を選ぶ役割を担います。

木に選ばれなかった正の辺を削除しても、選ばれた木が残るためグラフは連結です。反対に、接続に必要な正の辺を別の選び方でより低い合計コストにできるなら、Kruskalの木が最小コストであることに反します。負辺はすべて残し、0の辺は報酬を変えないため、同じ成分を結んでいた正の辺の合計が最大報酬になります。

辺のソートは O(M log M) 時間、Union-Findの処理は償却 O(M α(N)) 時間です。合計時間計算量は O(M log M + M α(N))、辺リストとUnion-Find配列を合わせたメモリ計算量は O(M + N) です。

辺の符号・自己ループ・平行辺と入力条件

• 負の辺：削除すると罰金になるため、Kruskalで接続用に選ばれなくても残します。
• 0の辺：削除しても残しても報酬は変わりません。コードは報酬に加算しません。
• 正の辺：両端がすでにつながっていれば削除し、コストを報酬へ加えます。別成分をつなぐ辺なら残します。

公式サンプル2はコスト1、0、-1の三角形で、負辺と0辺を含む接続を残し、正の辺1を削除するため出力は 1 です。サンプル3では、コスト-1の辺が頂点1と2をつなぎ、平行なコスト2の辺を削除して2を得ます。自己ループ (1, 1, 3) は最初から両端が同じ頂点なので削除でき、合計は 2 + 3 = 5 です。

問題では自己ループと平行辺が許され、元のグラフは連結と保証されています。制約は 2 ≤ N ≤ 2 × 10^5、N - 1 ≤ M ≤ 2 × 10^5、-10^9 ≤ C_i ≤ 10^9 です。非連結グラフはこの問題の入力条件に含まれません。