最初に全ての辺を削除して報酬をもらってしまい、「辺 \(i\) を元に戻す(削除しない)場合 \(C_i\) の罰金」と考えることにします。元の問題は罰金を最小化してグラフを連結にする問題と読み替えることができるため、辺 \(i\) の重みを \(C_i\) としたときの最小全域木を求めることで解くことができます。

ただし、\(C_i<0\) の辺は最小全域木に含まれなかった場合でも削除しないことに注意してください。

なおこの問題は「\(C_i\) が大きな辺から順に、その辺を削除しても連結なままなら削除する」という貪欲法でも正しい答えを得ることができますが、辺を削除した際の連結性の判定を高速に行うには高度なアルゴリズムが必要となります。