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

Subtask 1

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

Time Complexity: $\mathcal{O}(1)$ ~\mathcal{O}(1)~

Subtask 2

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

Subtask 3

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

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

Comments

There are no comments at the moment.