Minimum cut

Split the nodes of a flow network into two groups, S holding the source s and T holding the sink t. That split is an s-t cut. Its capacity is the total capacity of the edges that go from S to T; edges going from T back to S don't count.

Every unit of flow starts in S and ends in T, so it crosses from S to T at least once, and the edges it crosses on can carry no more than their capacity. So any flow is at most the capacity of any cut. A minimum cut is a cut of the smallest capacity: the narrowest wall between s and t.

The max-flow min-cut theorem says the two meet: the maximum flow equals the capacity of a minimum cut. The proof is the end of a maximum flow run. When the search in the residual graph can no longer reach t, let S be the nodes it did reach. Every edge from S to T must be full, or the search would have crossed it, and every edge from T to S must carry nothing, or its reverse edge would have let the search cross. So the flow crossing the wall is exactly the cut's capacity, and neither can improve.

The code is the Edmonds-Karp loop from Maximum flow, with its search steps run silently. When a search fails, the tinted nodes are the ones it reached. The cut is every original edge from a tinted node to an untinted one.

Both cut edges have 0 room left: they are full. That is not luck: an edge out of S with room left would have let the search continue.

This network has an edge from d back to c. After the flow is found, c is on the reached side and d is not, so d→c points from T to S. It doesn't block anything going from s to t, and the cut's capacity leaves it out. Adding up the original capacities of the S-to-T edges gives the maximum flow again.

The minimum cut is not always unique, and it is not simply the smallest edges: in this network the cheapest single edge, d→c, isn't in it at all. Finding one costs one maximum flow plus one more search.

Minimum cuts answer "choose a set" questions. Projects earn money, tools cost money, and a project can only run if every tool it needs is bought. Which projects should you take?

Build a network: s → each project with its profit, each project → each tool it needs with a huge capacity, each tool → t with its cost. In a finite cut, a project on the s side is chosen and every tool it needs is on the s side too, since cutting a huge edge is never cheapest. The cut pays the profit of every project left out plus the cost of every tool bought, so the best total is the sum of all profits minus the minimum cut.

Project q alone would lose money, since its tools cost 5 against a profit of 4. Next to p it shares tool y, which is already paid for, and the cut sees that without trying every combination. The same construction splits pixels into foreground and background, and assigns jobs to machines.

LeetCode has few problems that need a flow algorithm: most problems that look like one are solved by matching, a plain search or bitmask dynamic programming, so the practice list below is short.