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.

Authors: wleung_bvg

Solution Sketch

Subtask 1

A key observation is that at least N - 1 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 \max{}(0, N - 1 - M). You don't even need to read the full input!

Time Complexity: \mathcal{O}(1)

Subtask 2

For the second subtask, a key observation is that the number of additional pipes is equal to C - 1 where C 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: \mathcal{O}(N + M) or \mathcal{O}(N + M \cdot \alpha{}(N))

Subtask 3

For the third subtask, a key observation is that if a connected component has V vertices, then only V - 1 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 L be the number of such edges that can be moved and C be the number of connected components. Recall that C - 1 edges are required to connected all the connected components. Thus, the answer is equal to \max{}(0, C - 1 - \min{}(K, L)).

Time Complexity: \mathcal{O}(N + M) or \mathcal{O}(N + M \cdot \alpha{}(N))


Comments

There are no comments at the moment.