最大流增广路

from collections import deque

cap = {(0, 1): 3, (0, 2): 2, (1, 2): 1, (1, 3): 2, (2, 3): 4}

def max_flow(s, t):
    flow = 0
    residual = dict(cap)
    while True:
        parent = {s: None}
        q = deque([s])
        while q and t not in parent:
            u = q.popleft()
            for (a, b), c in residual.items():
                if a == u and c > 0 and b not in parent:
                    parent[b] = a
                    q.append(b)
        if t not in parent:
            return flow
        path, cur = [], t
        while cur != s:
            path.append((parent[cur], cur))
            cur = parent[cur]
        add = min(residual[e] for e in path)
        for a, b in path:
            residual[(a, b)] -= add
            residual[(b, a)] = residual.get((b, a), 0) + add
        flow += add

print(max_flow(0, 3))