ZERO / HERO
Water through pipes

Max Flow & Min Cut

The analogy

Pipes of different widths run from a reservoir to a town. How much water can flow at once? Not the sum of the pipes — the bottleneck decides. And here is the beautiful part: the maximum you can push equals the cheapest set of pipes you would have to cut to stop the water entirely.

Visualizer

Pushing flow, finding the cut

step 1 / 10
SABCDT

Pipes from source S to sink T. Capacities: S-A 10, S-B 5, A-C 4, A-D 8, B-D 6, C-T 10, D-T 7.capacities on each pipe

from collections import deque

def bfs_augment(cap, s, t, parent):
    parent.clear()
    parent[s] = None
    q = deque([s])
    while q:
        u = q.popleft()
        for v, c in cap[u].items():
            if c > 0 and v not in parent:
                parent[v] = u
                if v == t:
                    return True
                q.append(v)
    return False

def edmonds_karp(cap, s, t):
    flow, parent = 0, {}
    while bfs_augment(cap, s, t, parent):
        # bottleneck along the found path
        v, push = t, float("inf")
        while parent[v] is not None:
            u = parent[v]
            push = min(push, cap[u][v]); v = u
        v = t
        while parent[v] is not None:
            u = parent[v]
            cap[u][v] -= push
            cap[v][u] = cap[v].get(v, 0) + push   # RESIDUAL edge
            v = u
        flow += push
    return flow
Check yourself

What does the max-flow min-cut theorem let you compute for free?