1755. The Most That Can Reach the Sink

A DIRECTED network has n junctions and m pipes. Pipe i runs from u to v and carries at most c units per second; it carries nothing in the other direction. Print the greatest number of units per second that can flow from junction s to junction t.

A flow is valid when no pipe carries more than its capacity and every junction other than s and t sends out exactly as much as it takes in.

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

Two units go along 1->2->4 and two along 1->3->4. The pipe 1->2 could carry three, but 2->4 only takes two, so the third unit has nowhere to go.

## The three things that have to be said

directed? yes. A pipe from u to v does nothing for v to u. self-loops? allowed, and a pipe from a junction to itself can never carry flow, because the unit would have to both leave and arrive at the same place. parallel pipes? allowed. Two pipes from u to v of capacities 4 and 5 give a combined 9, and a solution that keeps one capacity per ORDERED PAIR silently throws one of them away. both directions? allowed. u to v and v to u may both be listed. disconnected? allowed. If t is unreachable from s the answer is 0.

## What most people try first

Find any route from s to t that still has spare capacity, push as much as that route allows, and repeat. That is the right shape and it is wrong as stated, because a route taken greedily can block a better pair of routes and nothing undoes it:

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

Push one unit along 1->2->3->4 and both remaining pipes out of 1 and into 4 are stranded: the answer drops to 1 when it should be 2.

## The fix, and it is one line

When you push x units along a pipe, reduce that pipe's remaining capacity by x AND increase its reverse direction's remaining capacity by x. The reverse entry is not a real pipe. It is permission to CANCEL x units of the flow you already committed, and that is what lets a later route undo an earlier mistake. With it the greedy becomes exact, and the proof is that when no route with spare capacity remains, the reachable set from s is a cut whose capacity equals the flow, so no flow can be larger.

## The method, Edmonds-Karp

build each pipe as two entries: capacity c forward, capacity 0 backward repeat: breadth-first search from s using only entries with capacity left if t was not reached: stop x = the smallest remaining capacity along the route found for every entry on the route: subtract x, and add x to its partner total += x

Choosing the route by BREADTH-FIRST SEARCH rather than any search is what makes the running time safe. With a shortest route each time the number of rounds is at most n * m / 2, independent of the capacities.

## Cost

O(n * m * m) time, which at n = 100 and m = 500 is 2.5 * 10^7.

## The size of the answer

Up to 500 pipes each carrying 10^9 can leave s, so the total can reach 5 * 10^11. A signed 32-bit integer stops at 2147483647, so the running total must be 64-bit. The individual capacities are fine in 32 bits; it is only the sum that is not.

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 - the same ordered pair may be listed more than once, so parallel pipes can occur, and both `u` to `v` and `v` to `u` may be present - the network may be disconnected