Let’s first remove all the edges and receive the reward, and consider that “we have to pay a fine of \(C_i\) when restoring (decide not to remove) Edge \(i\).” Then the original problem can be boiled down to a problem to minimize the amount of fine required to make the graph connected, which can be solved by finding the minimum spanning tree of graph with the cost of Edge \(i\) defined as \(C_i\).

Note that we do not remove the edges \(C_i<0\) even if it is not included in the minimum spanning tree.

Note that this problem can also be solved greedily by “inspecting the edge in the decreasing order of \(C_i\), and remove it if the graph remains connected after removing the edge.” However an advanced algorithm is required to determine the connectivity after removing an edge fast enough.