Min Cut and Matching

Max flow isn't just about pushing liquid through pipes. The max-flow min-cut theorem connects flow to cuts. Bipartite matching reduces to flow. And dozens of seemingly unrelated problems become flow problems once you learn to spot the pattern.

The Max-Flow Min-Cut Theorem

Max-flow equals min-cut: cut edges separate source and sink

A cut \((S, T)\) partitions the vertices into two sets: \(S\) containing the source and \(T\) containing the sink. The capacity of the cut is the sum of capacities of edges going from \(S\) to \(T\).

Theorem: The maximum flow from \(s\) to \(t\) equals the minimum cut capacity.

This isn't obvious. It says the bottleneck of the network (min cut) exactly determines the maximum throughput (max flow). No more, no less.

Key insight. Think of the min cut as the cheapest way to completely block all flow from \(s\) to \(t\). You're looking for the weakest "wall" that separates source from sink.

Finding the Min Cut

After running max flow (Dinic's), the min cut is easy to extract:

BFS from \(s\) in the residual graph (edges with residual capacity > 0).
Let \(S\) = set of reachable nodes, \(T\) = unreachable nodes.
The min cut edges are original edges from \(S\) to \(T\) that are fully saturated.

vector<pair<int,int>> findMinCut(Dinic& d, int s) {
    int n = d.graph.size();
    vector<bool> reach(n, false);
    queue<int> q;
    reach[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto& e : d.graph[u]) {
            if (e.cap > 0 && !reach[e.to]) {
                reach[e.to] = true;
                q.push(e.to);
            }
        }
    }
    vector<pair<int,int>> cut;
    for (int u = 0; u < n; u++) {
        if (!reach[u]) continue;
        for (auto& e : d.graph[u]) {
            if (!reach[e.to] && e.cap == 0)
                cut.push_back({u, e.to});
        }
    }
    return cut;
}

CSES Police Chase

Problem. A city has \(N\) intersections and \(M\) streets (undirected). Find the minimum number of streets to block so that there is no path from intersection 1 to intersection \(N\). Output the blocked streets.

This is a min cut problem. Each undirected edge becomes two directed edges (both directions) with capacity 1.

#include <bits/stdc++.h>
using namespace std;

struct Edge { int to, rev; long long cap; };

struct Dinic {
    vector<vector<Edge>> graph;
    vector<int> level, iter;
    Dinic(int n) : graph(n), level(n), iter(n) {}
    void addEdge(int f, int t, long long c) {
        graph[f].push_back({t,(int)graph[t].size(),c});
        graph[t].push_back({f,(int)graph[f].size()-1,0});
    }
    bool bfs(int s, int t) {
        fill(level.begin(),level.end(),-1);
        queue<int> q; level[s]=0; q.push(s);
        while(!q.empty()){int v=q.front();q.pop();
        for(auto&e:graph[v])if(e.cap>0&&level[e.to]<0){level[e.to]=level[v]+1;q.push(e.to);}}
        return level[t]>=0;
    }
    long long dfs(int v,int t,long long f){
        if(v==t)return f;
        for(int&i=iter[v];i<(int)graph[v].size();i++){
        Edge&e=graph[v][i];
        if(e.cap>0&&level[v]<level[e.to]){long long d=dfs(e.to,t,min(f,e.cap));
        if(d>0){e.cap-=d;graph[e.to][e.rev].cap+=d;return d;}}}return 0;
    }
    long long maxflow(int s,int t){
        long long flow=0;while(bfs(s,t)){fill(iter.begin(),iter.end(),0);
        long long d;while((d=dfs(s,t,LLONG_MAX))>0)flow+=d;}return flow;
    }
};

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    Dinic d(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        d.addEdge(a, b, 1);
        d.addEdge(b, a, 1);
    }
    long long flow = d.maxflow(1, n);
    // Find cut
    vector<bool> reach(n + 1, false);
    queue<int> q;
    reach[1] = true; q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto& e : d.graph[u])
            if (e.cap > 0 && !reach[e.to]) { reach[e.to] = true; q.push(e.to); }
    }
    printf("%lld\n", flow);
    for (int u = 1; u <= n; u++) {
        if (!reach[u]) continue;
        for (auto& e : d.graph[u]) {
            if (!reach[e.to] && e.to != 0) {
                printf("%d %d\n", u, e.to);
            }
        }
    }
}

Gotcha. For undirected edges, add both directions with capacity 1. Don't add them as a single bidirectional edge with capacity 2 -- that would let 2 units of flow use the same street.

Bipartite Matching via Max Flow

Bipartite matching via max-flow: source, left nodes, right nodes, sink

Problem. Given a bipartite graph with left nodes \(L\) and right nodes \(R\), find the maximum matching (largest set of edges with no shared endpoints).

Reduction to max flow:

Create a source \(s\) connected to every left node with capacity 1.
Create a sink \(t\) connected from every right node with capacity 1.
For each edge \((l, r)\) in the bipartite graph, add edge \(l \to r\) with capacity 1.
Max flow = max matching.

The capacity-1 constraints ensure each node is matched at most once.

CSES School Dance

Problem. \(N\) boys and \(M\) girls. Some pairs are willing to dance together. Find the maximum number of pairs, and output the pairing.

#include <bits/stdc++.h>
using namespace std;

struct Edge { int to, rev; long long cap; };
struct Dinic {
    vector<vector<Edge>> graph;
    vector<int> level, iter;
    Dinic(int n):graph(n),level(n),iter(n){}
    void addEdge(int f,int t,long long c){
        graph[f].push_back({t,(int)graph[t].size(),c});
        graph[t].push_back({f,(int)graph[f].size()-1,0});}
    bool bfs(int s,int t){fill(level.begin(),level.end(),-1);
        queue<int>q;level[s]=0;q.push(s);while(!q.empty()){int v=q.front();q.pop();
        for(auto&e:graph[v])if(e.cap>0&&level[e.to]<0){level[e.to]=level[v]+1;q.push(e.to);}}
        return level[t]>=0;}
    long long dfs(int v,int t,long long f){if(v==t)return f;
        for(int&i=iter[v];i<(int)graph[v].size();i++){Edge&e=graph[v][i];
        if(e.cap>0&&level[v]<level[e.to]){long long d=dfs(e.to,t,min(f,e.cap));
        if(d>0){e.cap-=d;graph[e.to][e.rev].cap+=d;return d;}}}return 0;}
    long long maxflow(int s,int t){long long flow=0;while(bfs(s,t)){
        fill(iter.begin(),iter.end(),0);long long d;
        while((d=dfs(s,t,LLONG_MAX))>0)flow+=d;}return flow;}
};

int main() {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    // boys: 1..n, girls: n+1..n+m, source: 0, sink: n+m+1
    int src = 0, snk = n + m + 1;
    Dinic d(n + m + 2);
    for (int i = 1; i <= n; i++) d.addEdge(src, i, 1);
    for (int j = 1; j <= m; j++) d.addEdge(n + j, snk, 1);
    for (int i = 0; i < k; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        d.addEdge(a, n + b, 1);
    }
    long long ans = d.maxflow(src, snk);
    printf("%lld\n", ans);
    // Extract matching: for each boy, find the edge to a girl with 0 residual
    for (int i = 1; i <= n; i++) {
        for (auto& e : d.graph[i]) {
            if (e.to > n && e.to <= n + m && e.cap == 0) {
                printf("%d %d\n", i, e.to - n);
                break;
            }
        }
    }
}

Key insight. Dinic's on unit-capacity bipartite graphs runs in \(O(E\sqrt{V})\), which is the same complexity as the Hopcroft-Karp algorithm. You get optimal bipartite matching speed "for free" from the Dinic template.

CSES Distinct Routes

Problem. Find the maximum number of edge-disjoint paths from node 1 to node \(N\), and print the paths.

Edge-disjoint paths = max flow with capacity 1 on each edge. After computing flow, decompose into individual paths by repeatedly walking from source to sink along saturated edges.

// After computing max flow with cap-1 edges:
// Path decomposition
vector<vector<int>> paths;
while (true) {
    vector<int> path;
    int cur = 1;
    path.push_back(cur);
    while (cur != n) {
        bool found = false;
        for (auto& e : d.graph[cur]) {
            // Original edge that carried flow: residual cap < original cap
            // For cap-1 edges: original cap was 1, so residual is 0 if flow passed
            if (e.to != 0 && e.cap == 0 && /* is forward edge */) {
                e.cap = 1; // restore so we don't reuse
                cur = e.to;
                path.push_back(cur);
                found = true;
                break;
            }
        }
        if (!found) break;
    }
    if (path.back() != n) break;
    paths.push_back(path);
}

The trick is identifying forward edges. Since addEdge creates them in pairs, forward edges are at even indices in the edge list when added carefully. An alternative: store a boolean isForward in the Edge struct.

The Art of Flow Modeling

Many problems that don't mention "flow" are secretly flow problems. The key skill is recognizing the reduction.

Common patterns:

Real Problem	Flow Model
Max bipartite matching	Source → left, right → sink, cap 1
Edge-disjoint paths	Cap 1 on each edge
Node-disjoint paths	Split each node into in-node and out-node, cap 1 edge between
Min vertex cut	Node splitting + min cut
Assignment problem	Bipartite matching with costs (min-cost max flow)

Node splitting deserves extra attention. To limit flow through a node \(v\) to at most \(c\) units, replace \(v\) with two nodes \(v_{in}\) and \(v_{out}\). All incoming edges go to \(v_{in}\). All outgoing edges leave from \(v_{out}\). Add edge \(v_{in} \to v_{out}\) with capacity \(c\).

Gotcha. When the problem says "remove minimum number of nodes to disconnect \(s\) from \(t\)," that's a min node cut. You must split nodes. If you forget the splitting and just run min edge cut, you'll get the wrong answer.

Problems

Problem	Link	Difficulty
CSES Police Chase	cses.fi/problemset/task/1695	Medium
CSES School Dance	cses.fi/problemset/task/1696	Medium
CSES Distinct Routes	cses.fi/problemset/task/1711	Hard