1767. The Worst Junction To Lose

A DIRECTED network has n junctions and m pipes, pipe i running from u to v with capacity c. Exactly ONE junction other than s and t is going to fail, and when a junction fails every pipe touching it is lost. An adversary picks which.

Print the maximum flow from s to t that survives the worst single failure, that is, the SMALLEST maximum flow over all choices of the failing junction. If n is 2 there is no junction available to fail, so print the unchanged maximum flow.

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

The flow is 10. Failing junction 2 loses 1->2 and 2->4, leaving 5. Failing junction 3 leaves 5 as well. So the answer is 5.

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

The flow is 6. Failing junction 2 leaves only 1->4, so the answer is 1. Junction 3 does not exist in the first place; with n = 4 and no pipes touching junction 3, failing it changes nothing, so the adversary would not choose it.

## What most people try first

Run the flow once, total what each junction passes, and fail the busiest.

s=1 t=5: 1->6 cap 10, 6->2 cap 10, 6->3 cap 10, 2->5 cap 10, 3->5 cap 10

The flow is 10 and it all goes 1->6->2->5, so junction 6 and junction 2 each pass 10 while junction 3 passes nothing. A rule that fails the busiest junction may well pick junction 2, and failing junction 2 leaves 10, because the flow simply reroutes through junction 3. Failing junction 6 leaves NOTHING. So the rule reports 10 where the answer is 0.

And which of 6 and 2 counts as busiest, or whether the flow went through 2 or through 3 at all, depends on the order the search examined the arcs. Problem 1766 makes the same point about pipes: an answer that depends on a correct implementation's internal choices is not an answer.

The second attempt is to fail every PAIR, or every SUBSET, of junctions. That answers a different question; exactly one junction fails here.

## The method

Recompute. For each junction v other than s and t, delete every pipe with u = v or v = v, run the maximum flow, and keep the smallest result.

best = infinity for v in 1 .. n, v not s and not t: best = min(best, maxflow(pipes not touching v)) if no such v existed: best = maxflow(all pipes)

The constraints are set so this is the intended solution: at most 28 flow computations with n = 30 and m = 100.

## Why "smallest over choices" rather than "the flow minus something"

There is no quantity you can subtract. Removing a junction can drop the flow by far more than that junction's own throughput, because the pipes around it may be the only ones its neighbours had, and it can also drop the flow by nothing at all. The minimum over the n - 2 recomputations is the definition and there is no shortcut at this size.

## Cost

At most n - 2 runs of O(n * m * m), so O(n * n * m * m), which at n = 30 and m = 100 is 9 * 10^6. The answer can reach 100 * 10^9 = 10^11, so the total has to be held in 64 bits: a signed 32-bit integer stops at 2147483647, and overflow here would silently produce a negative flow.

Constraints - `2 ≤ n ≤ 30` - `0 ≤ m ≤ 100` - `1 ≤ u, v ≤ n` - `1 ≤ c ≤ 1000000000` - `1 ≤ s, t ≤ n` and `s ≠ t`, so `n` is never 1 - exactly one junction fails, and it is never `s` or `t` - the limits allow the intended solution of up to `n - 2` separate flow computations - self-loops and parallel pipes can occur, and the network may be disconnected