グラフ\(G\) に対して， \(I \subset E(G)\) が connected であるとは， \(I\) により定まる \(G\) の subgraph が connected であるときをいう．
以下，\(G\) を与えられたグラフとする．\( E := E(G)\), \(E^{-}\)を，\(E\) における負のコストの辺全体 とする． \(J \subset E\) を削除する辺全体とする． \[ \begin{array}[rcl]{} ans_{G} &=& max_{J \subset E, E-J: connected}(\sum_{e \in J} cost_{e}) \\ &=& max_{J \subset E - E^{-}, E-J: connected}(\sum_{e \in J} cost_{e}) \\ &=& max_{J \subset E - E^{-}, E-J: connected} (\sum_{e \in E} cost_{e} - \sum_{e \in E - J} cost_{e}) \\ &=& \sum_{e \in E} cost_{e} + max_{J \subset E - E^{-}, E-J: connected} ( - \sum_{e \in E - J, E-J} cost_{e}). \end{array} \] ここで \(I := E - J\) とおくと， \[ \begin{array}[rcl] ans_{G} &=& \sum_{e \in E} cost_{e} - min_{E-I \subset E-E^{-}: I: connected} ( \sum_{e \in E - J} cost_{e}) \\ &=& \sum_{e \in E} cost_{e} - min_{E^{-} \subset I, I: connected} ( \sum_{e \in I} cost_{e}) \\ \end{array} \] となる．
よって，MST を求めるのと同様にできるので，クラスカル法で求める．\(E^{-}\) の辺は，連結性とは無関係に使うことに注意．
実装:
本当は，必ず使う辺だけ merge しておくべき． 今回は，ソートしたときに \(c < 0 \) の辺が先に来るので問題ない．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
