1761. When the Junctions Have Limits Too

A DIRECTED network has n junctions and m pipes, pipe i running from u to v with capacity c. This time the JUNCTIONS have limits too: junction v can pass at most w units per second through itself, and that applies to the source and the sink as well, so w[s] caps what can leave and w[t] caps what can arrive.

Print the greatest flow from s to t.

pipes: 1->2 cap 9, 2->3 cap 9 limits: w1 = 9, w2 = 4, w3 = 9 -> 4

Both pipes allow 9 but junction 2 only passes 4.

## What most people try first

Replace each junction's limit by capping the pipes around it: set every pipe into v and out of v to at most w[v]. That is wrong in both directions.

pipes: 1->2 cap 5, 1->3 cap 5, 2->4 cap 5, 3->4 cap 5 limits: w1 = 10, w2 = 10, w3 = 10, w4 = 6

Nothing needs capping, since every pipe's capacity is already below every relevant limit, so the method answers 10. But junction 4 passes only 6, so the answer is 6. Capping pipes cannot express a limit on a junction with several pipes, because the limit is on the TOTAL through it, not on any one pipe.

The second attempt is to subtract the overflow by hand, which has no consistent rule once a junction has both several pipes in and several out.

## The method: split every junction in two

Give junction v two nodes, an arrival node v and a departure node v + n, and one arc between them:

arc v -> v + n of capacity w[v]

Then every pipe u -> v of capacity c becomes an arc from u's DEPARTURE node to v's ARRIVAL node of capacity c. Run a maximum flow from s's ARRIVAL node to t's DEPARTURE node.

Every unit of flow that passes through v has to cross v's single internal arc, so the total through v is at most w[v], which is exactly the rule. And because the source is s's arrival node and the sink is t's departure node, the flow also crosses s's and t's internal arcs, so their limits bind too. Sourcing at s + n instead would silently ignore w[s], and that is the error to watch for.

## The three things that have to be said

directed? yes. self-loops? allowed. A self-loop becomes v + n -> v, a step backwards through the junction, and it can never carry flow. parallel pipes? allowed, and their capacities add, but the junction limit at either end still caps the total. disconnected? allowed; the answer is 0 when t is unreachable.

## Cost

The split network has 2n nodes and m + n arcs, so Edmonds-Karp costs O(n * (m + n) * (m + n)). At n = 100 and m = 500 that is about 7 * 10^7.

## The size of the answer

A junction limit can be as large as 10^12, which already exceeds the 2147483647 a signed 32-bit integer holds, so the capacities themselves need 64 bits and not only their sum. The flow is bounded by w[s] and by the total capacity leaving s, so at most min(10^12, 500 * 10^9) = 5 * 10^11.

Constraints - `2 ≤ n ≤ 100` - `0 ≤ m ≤ 500` - `1 ≤ u, v ≤ n` - `1 ≤ c ≤ 1000000000` - `1 ≤ w ≤ 1000000000000`, so a single junction limit already exceeds what a signed 32-bit integer holds - `1 ≤ s, t ≤ n` and `s ≠ t`, so `n` is never 1 - the junction limits apply to `s` and `t` as well as to the junctions in between - self-loops and parallel pipes can occur, and the network may be disconnected