## Editorial for Wesley's Anger Contest 1 Problem 2 - A Minimum Cost Flow Problem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: wleung_bvg

#### Solution Sketch

A key observation is that at least pipes are needed to connect all buildings. In addition, the location of the water pump does not matter. For the first subtask, all pipes can be moved to a different location, thus the answer is . You don't even need to read the full input!

Time Complexity: For the second subtask, a key observation is that the number of additional pipes is equal to where is the number of connected components in the graph. This can be computed in a number of ways, including breadth first search, depth first search, of the union find data structure.

Time Complexity: or For the third subtask, a key observation is that if a connected component has vertices, then only edges are required to keep it connected. All other edges should be moved. Specifically, these edges should be moved to connect two connected components. These edges can be computed in a similar manner to subtask 2. Let be the number of such edges that can be moved and be the number of connected components. Recall that edges are required to connected all the connected components. Thus, the answer is equal to .
Time Complexity: or 