1757. Which Side of the Split

A DIRECTED network has n junctions and m pipes, pipe i running from u to v with capacity c. Problem 1756 asks for the cost of the cheapest way to shut t off from s. This asks WHERE the cut runs: for every junction, print 1 if it ends up on the source's side and 2 if it ends up on the sink's side.

A split is a way of putting every junction into one of two groups with s in group 1 and t in group 2. Its cost is the total capacity of the pipes running from group 1 to group 2; pipes running the other way cost nothing, which is the detail that catches people out.

## The answer is pinned, because the cheapest split is usually not unique

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

Both {1} against {2,3} and {1,2} against {3} cost 1. Printing either would make the problem ambiguous, so this problem asks for the cheapest split whose group 1 is smallest: the one whose source side is contained inside the source side of every other cheapest split.

That set exists and is unique. If two cheapest splits have source sides A and B, their intersection is also a cheapest split, so intersecting all of them gives one, and by construction nothing cheaper has a smaller source side. For the example above, the answer is 1 2 2.

## What most people try first

Breadth-first search from s on the original network and call everything reached group 1. That answers 1 1 1 above, which is not even a split, because t must be in group 2. The reachable set only works on the RESIDUAL network after a maximum flow, and the difference between those two is the whole lesson.

The second attempt is every subset of junctions. 2^98 for n = 100.

## The method

run Edmonds-Karp to get the maximum flow from s to t then search from s again, but only along entries with capacity LEFT, counting the reverse permissions the augmenting steps created everything reached is group 1; everything else is group 2

## Why this is the smallest source side

t is not reached, or another augmenting route would exist and the flow would not be maximum. Every pipe from the reached set outward has no capacity left, so it is full; every pipe from outside into the reached set carries nothing, or its reverse permission would have let the search out. So the split's cost equals the flow, which makes it cheapest.

And it is the smallest: take any cheapest split with source side A. Every pipe leaving A is full and every pipe entering A is empty, since the flow across A equals its cost and nothing may be wasted. So no residual entry leaves A, which means the search from s never escapes A, so the reached set is inside A. True for every cheapest split, so it is inside all of them.

## Cost

O(n * m * m), which at n = 100 and m = 500 is 2.5 * 10^7. Only the flow total needs 64 bits; the output is just 1 and 2.

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 - self-loops and parallel pipes can occur, and both `u` to `v` and `v` to `u` may be present - the network may be disconnected, in which case group 1 is just the part reachable from `s`