1756. The Cheapest Way To Shut the Sink Off

A DIRECTED network has n junctions and m pipes, pipe i running from u to v with capacity c. You want to shut the sink off from the source: choose a set of pipes to destroy so that afterwards there is NO directed route at all from s to t. Destroying pipe i costs c. Print the smallest total cost.

The answer is the CUT, not the flow. That distinction is the whole point of this problem.

1->2 cap 3, 1->3 cap 2, 2->4 cap 2, 3->4 cap 4 s=1 t=4 -> 4

Destroy 2->4 and 1->3, cost 2 + 2 = 4, and nothing is left: every route runs through one of them. Destroying 1->2 and 1->3 costs 3 + 2 = 5, which also works and is worse.

## What most people try first

Destroy the cheapest pipes until t is unreachable. That is wrong, and this network shows it:

1->2 cap 1, 2->3 cap 1, 1->3 cap 1, 3->4 cap 5 s=1 t=4

The three cheap pipes all cost 1 and the expensive one costs 5, so cheapest first destroys 1->2, 2->3 and 1->3, cost 3. But destroying only 3->4 costs 5... and in fact cutting 1->2 and 1->3 costs 2 and finishes the job, which cheapest-first misses because after removing 1->2 it goes for 2->3, a pipe that is no longer on any route.

The second attempt is to try every subset of pipes. Correct, and 2^m subsets at m = 500 is not a number you can reach.

## The method

Compute the MAXIMUM FLOW from s to t and print it. That is the answer.

That is not a coincidence and it is not an approximation. Every cut is an upper bound on every flow, because all the flow has to cross it, so

max flow <= min cut

always. For the other direction, run the flow to completion and look at the residual network, meaning each pipe's leftover capacity plus the reverse permissions the augmenting steps created. Let S be the junctions still reachable from s there. Then t is not in S, or another route would exist and the flow would not be finished. Every pipe from S to outside S has zero leftover, so it is carrying its full capacity, and every pipe from outside into S is carrying nothing, or its reverse permission would have let the search leave S. So the flow across that cut equals the cut's capacity exactly, giving

min cut <= capacity of this cut = flow <= max flow

and the two bounds meet. Problem 1755 asks for the flow with the same input format; this asks for the number it is equal to, and problem 1758 asks which pipes the cut consists of.

## Cost

Edmonds-Karp, O(n * m * m), which at n = 100 and m = 500 is 2.5 * 10^7. The answer can reach 5 * 10^11, so the total needs 64 bits; 2147483647 is where a signed 32-bit integer stops.

Constraints - `2 ≤ n ≤ 100` - `0 ≤ m ≤ 500` - `1 ≤ u, v ≤ n` - `1 ≤ c ≤ 1000000000` - `1 ≤ s, t ≤ n` and `s ≠ t`, so `n` is never 1 - `u` may equal `v`, so self-loops can occur, and a self-loop never needs destroying - parallel pipes can occur, and both `u` to `v` and `v` to `u` may be present - the network may be disconnected, in which case the answer can be 0