Maximum Flow

Given a directed graph with edge capacities, a source $s$ and a sink $t$ , push as much flow as possible from $s$ to $t$ subject to capacity limits and conservation at every other vertex.

Max-Flow Min-Cut Theorem

The maximum flow value equals the minimum capacity of an $s$ - $t$ cut.

This is why so many problems reduce to flow: anything phrased as “minimum cost to separate” or “maximum number of disjoint things” is one of the two sides of this equality.

Which algorithm

Algorithm	Time	Use
Ford-Fulkerson	$O (E F)$	never — pseudo-polynomial
Edmonds-Karp	$O (V E^{2})$	teaching
Dinic	$O (V^{2} E)$ ; $O (E V)$ unit caps	the default
Push-relabel (highest label + gap)	$O (V^{2} E)$	dense graphs, huge capacities
MPM	$O (V^{3})$	dense graphs

Write Dinic. Its worst case is pessimistic; on bipartite matching it is provably $O (E V)$ , and on typical contest graphs it is far faster than its bound.

Dinic

struct Dinic {
    struct E { int to; long long cap; };
    vector<E> es;
    vector<vector<int>> g;
    vector<int> level, it;
    int n;
 
    Dinic(int n) : g(n), level(n), it(n), n(n) {}
    void addEdge(int u, int v, long long c) {
        g[u].push_back(es.size()); es.push_back({v, c});
        g[v].push_back(es.size()); es.push_back({u, 0});   // reverse, cap 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 u = q.front(); q.pop();
            for (int id : g[u])
                if (es[id].cap > 0 && level[es[id].to] < 0) {
                    level[es[id].to] = level[u] + 1;
                    q.push(es[id].to);
                }
        }
        return level[t] >= 0;
    }
    long long dfs(int u, int t, long long f) {
        if (u == t) return f;
        for (int& i = it[u]; i < (int)g[u].size(); i++) {
            int id = g[u][i], v = es[id].to;
            if (es[id].cap <= 0 || level[v] != level[u] + 1) continue;
            long long d = dfs(v, t, min(f, es[id].cap));
            if (d > 0) { es[id].cap -= d; es[id ^ 1].cap += d; return d; }
        }
        return 0;
    }
    long long maxflow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            fill(it.begin(), it.end(), 0);
            while (long long f = dfs(s, t, LLONG_MAX)) flow += f;
        }
        return flow;
    }
};

Two details do all the work: storing each edge with its reverse at index id ^ 1, and the current-arc pointer it[u] which prevents re-scanning saturated edges within a phase.

Modelling patterns

Problem	Construction
Bipartite matching	$s \to L$ cap 1, $L \to R$ cap 1, $R \to t$ cap 1
Vertex capacities	split $v$ into $v_{in} \to v_{o u t}$ with that capacity
Multiple sources/sinks	super-source and super-sink with infinite edges
Vertex-disjoint paths	split vertices, capacities 1, answer = max flow
Edge-disjoint paths	capacities 1, answer = max flow (Menger)
Minimum path cover of a DAG	$V$ − maximum bipartite matching of the split graph
Maximum closure / project selection	profits from $s$ , costs to $t$ , prerequisites as $\infty$ edges; answer = total profit − min cut
Minimum vertex cover (bipartite)	= max matching (König); recover it from the min cut
Maximum independent set (bipartite)	$V$ − max matching
Assignment with capacities	capacities on the $s \to L$ and $R \to t$ edges
Lower bounds on edges	transform to a circulation problem

Project selection is the highest-value pattern: whenever the problem is “choose a set of items, some give profit, some cost, with ‘if you take $A$ you must take $B$ ’ constraints”, it is a min cut.

Recovering the min cut

After maxflow, BFS from $s$ in the residual graph. The reachable set $S$ and its complement $T$ form a minimum cut; the cut edges are those from $S$ to $T$ with zero residual capacity.

Integrality

With integer capacities, max flow has an integral optimal solution — which is why matching and disjoint-path problems get 0/1 answers for free. This fails for min-cost flow only when capacities are non-integral.

See also: Minimum Cut · Min-Cost Flow · Dinic

whoashish's cp notes

Directory