1762. Many Depots and Many Markets

A DIRECTED network has n towns and m pipes, pipe i running from u to v with capacity c. k of the towns are DEPOTS, which can each supply any amount, and l of them are MARKETS, which can each absorb any amount. Every other town must pass on exactly what it takes in.

Print the greatest total that can be delivered from the depots to the markets.

pipes: 1->3 cap 4, 2->3 cap 5, 3->4 cap 6, 3->5 cap 2 depots: 1 2 markets: 4 5 -> 8

Everything has to pass through town 3. Nine units can reach it, 4 along 1->3 and 5 along 2->3, but only 6 + 2 = 8 can leave it, so 8 is delivered and one unit of supply stays at the depots.

## What most people try first

Run a separate maximum flow from each depot and add the results. That over-counts badly, because two depots can compete for the same pipe and neither run knows about the other:

pipes: 1->3 cap 5, 2->3 cap 5, 3->4 cap 5 depots: 1 2 markets: 4

Each depot alone delivers 5, so adding gives 10. The real answer is 5, since 3->4 is the only way out.

The second attempt is to pick the single best depot and the single best market, which under-counts whenever two depots can be used at once.

## The method: one artificial source and one artificial sink

Add two new nodes, S and T. Put an arc from S to every depot and an arc from every market to T, each with a capacity too large to bind. Then compute the maximum flow from S to T in that enlarged network.

A unit of flow from S must enter the real network at a depot and leave it at a market, and conservation holds at every real town except the depots and markets, whose artificial arcs absorb the imbalance. So flows in the enlarged network and deliveries in the original are the same thing with the same value.

## How large is "too large to bind"

Derive it, do not guess. The delivery can never exceed the total capacity of all the pipes, so one more than that sum is enough:

inf = c1 + c2 + ... + cm + 1

At m = 500 and c = 10^9 that sum is 5 * 10^11, which is past 2147483647, so inf itself must be a 64-bit value: held in a 32-bit variable it overflows and stops being an upper bound on anything. Choosing a 32-bit "infinity" like 1000000000 is the classic failure: it is smaller than the real answer can be, so it becomes a genuine capacity and silently caps the result.

## The three things that have to be said

directed? yes. self-loops? allowed, never carry anything. parallel pipes? allowed, capacities add. disconnected? allowed, and the answer is 0 when no depot reaches any market. overlap? no town is both a depot and a market, which is why the answer is finite: a town that was both could absorb its own supply without limit.

## Cost

The enlarged network has n + 2 nodes and m + k + l arcs, so Edmonds-Karp costs O(n * (m + n) * (m + n)), about 7 * 10^7 at n = 100 and m = 500.

Constraints - `2 ≤ n ≤ 100` - `0 ≤ m ≤ 500` - `1 ≤ u, v ≤ n` - `1 ≤ c ≤ 1000000000` - `1 ≤ k` and `1 ≤ l` and `k + l ≤ n` - the depots are distinct, the markets are distinct, and no town is both, so the answer is always finite - self-loops and parallel pipes can occur, and the network may be disconnected