CONCEPT · Legendary
Max flow / min cut
also Dinic · Edmonds-Karp · Ford-Fulkerson
Maximum s-t flow equals minimum s-t cut. Augmenting paths on the residual graph find the flow. Matching and 'disconnect t from s' are reductions.
Intuition
You keep finding a leftover path and shoving as much as the bottleneck allows. Reverse edges let you change your mind.
When to reach for it
- Bipartite matching (source-left-right-sink)
- Edge-disjoint paths (unit capacities)
- Min edges/vertices to disconnect
- CSES Download Speed, School Dance, Police Chase
Usual pits
- Forgetting residual reverse edges
- EK/DFS on huge capacities — use Dinic
- n=2e5 — this is the wrong algorithm
- Undirected edges need both directions in the residual setup