Chapter 114

Home

Min-Cut Max-Flow Theorem

A cut partitions nodes into S (contains source) and T (contains sink). Cut capacity = sum of capacities from S to T. The min-cut max-flow theorem: the maximum flow equals the minimum cut capacity. Finding the min cut after running Dinic is trivial — the set of nodes reachable from source in the residual graph.

Finding the Min Cut

C++ — min cut after Dinic

// After running max_flow, nodes reachable from s with positive
// residual capacity form the S side of the min cut.
vector vis(n, false);
queue q; q.push(s); vis[s] = true;
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (auto& e : dinic.adj[u])
        if (e.cap > 0 && !vis[e.v]) {
            vis[e.v] = true;
            q.push(e.v);
        }
}
// vis[u] = true → node u is on source side of min cut
// All edges from vis=true to vis=false are cut edges

Key Takeaways