Maximum Flow

The problem

A directed graph where each edge has a capacity. Send as much as possible from a source to a sink without exceeding any capacity, and with flow conserved at every other node — whatever enters must leave.

The value of this technique is less about networks and more about what reduces to it. Bipartite matching, minimum vertex cover on bipartite graphs, and several partition problems are all max-flow in disguise.

Residual capacities and reverse edges

The central mechanism: alongside every edge, store a reverse edge with capacity zero. Pushing flow forward decreases the forward capacity and increases the reverse one, which lets a later augmentation undo an earlier bad choice.

Without reverse edges, a greedy first path can block the optimum permanently.

static int[] head, nxt, to;
static long[] cap;
static int edgeCount = 0;

static void init(int n, int m) {
    head = new int[n + 1];
    Arrays.fill(head, -1);
    nxt = new int[2 * m];
    to  = new int[2 * m];
    cap = new long[2 * m];
}

static void addEdge(int u, int v, long c) {
    to[edgeCount] = v; cap[edgeCount] = c;
    nxt[edgeCount] = head[u]; head[u] = edgeCount++;

    to[edgeCount] = u; cap[edgeCount] = 0;      // reverse, zero capacity
    nxt[edgeCount] = head[v]; head[v] = edgeCount++;
}

Adding edges in pairs means edge i and edge i ^ 1 are each other’s reverse — the XOR trick makes finding the partner free. That is why edges must always be added two at a time, never one.

For an undirected edge, give the reverse edge capacity c instead of 0.

Dinic’s algorithm

Repeatedly build a level graph by BFS, then push flow along shortest augmenting paths by DFS. Faster and more predictable than pushing one path at a time.

static int[] level, iter;
static int source, sink;

static boolean bfs() {
    level = new int[head.length];
    Arrays.fill(level, -1);
    Deque<Integer> q = new ArrayDeque<>();
    level[source] = 0;
    q.add(source);

    while (!q.isEmpty()) {
        int u = q.poll();
        for (int e = head[u]; e != -1; e = nxt[e]) {
            if (cap[e] > 0 && level[to[e]] < 0) {
                level[to[e]] = level[u] + 1;
                q.add(to[e]);
            }
        }
    }
    return level[sink] >= 0;
}

static long dfs(int u, long pushed) {
    if (u == sink || pushed == 0) return pushed;

    for (; iter[u] != -1; iter[u] = nxt[iter[u]]) {
        int e = iter[u], v = to[e];
        if (cap[e] <= 0 || level[v] != level[u] + 1) continue;

        long got = dfs(v, Math.min(pushed, cap[e]));
        if (got > 0) {
            cap[e]     -= got;
            cap[e ^ 1] += got;              // return capacity to the reverse edge
            return got;
        }
    }
    return 0;
}

static long maxFlow() {
    long total = 0;
    while (bfs()) {
        iter = head.clone();                // resume each node where it left off
        long pushed;
        while ((pushed = dfs(source, Long.MAX_VALUE)) > 0) {
            total += pushed;
        }
    }
    return total;
}

Complexity is O(V²E) in general, but O(E√V) on unit-capacity graphs, which is the bipartite matching case. In practice it handles graphs far larger than the bound suggests.

Bipartite matching

Given two groups and a list of compatible pairs, match as many as possible with each item used at most once.

Build a source connected to every left node with capacity 1, every compatible pair as capacity 1, and every right node to a sink with capacity 1. The maximum flow is the maximum matching.

// nodes: 0 = source, 1..L = left, L+1..L+R = right, L+R+1 = sink
init(L + R + 2, L + R + pairs.length);
source = 0;
sink = L + R + 1;

for (int i = 1; i <= L; i++) addEdge(source, i, 1);
for (int j = 1; j <= R; j++) addEdge(L + j, sink, 1);
for (int[] p : pairs) addEdge(p[0], L + p[1], 1);

System.out.println(maxFlow());

The capacity-1 edges from the source and to the sink are what enforce “used at most once”. Change them to k and each item may be used k times — a small edit that solves a noticeably different problem.

Max-flow min-cut

The maximum flow equals the minimum total capacity of edges whose removal disconnects source from sink. So any problem asking for a cheapest set of removals to separate two things is a max-flow problem.

To recover which edges form the cut, run the flow, then BFS from the source using only edges with remaining capacity. Reachable nodes form one side; edges crossing to unreachable nodes are the cut.

boolean[] reachable = new boolean[n + 1];
// BFS from source over edges with cap[e] > 0, marking reachable
// then any original edge u -> v with reachable[u] && !reachable[v] is in the cut

Problems that reduce to max flow

The third row is a standard trick worth knowing: to limit how often a node is used rather than an edge, split it into v_in and v_out joined by a single edge whose capacity is the limit. All incoming edges land on v_in, all outgoing leave v_out.

Related