Lab 13 — Min-Cost Max-Flow

Goal

Implement min-cost max-flow via successive shortest augmenting paths (SPFA/Bellman-Ford, or Dijkstra with Johnson potentials), and use it to solve assignment-shaped optimization problems exactly — the cost-aware sibling of Dinic (lab-01) and bipartite matching (lab-02).

Background

Add a cost per unit of flow to each edge; among all maximum flows, find the cheapest. The residual graph now carries costs: pushing flow on edge (u,v, cost c) creates a reverse residual edge (v,u, cost −c) — undoing flow refunds its cost. Those negative edges are why plain Dijkstra fails and Bellman-Ford/SPFA appears.

Successive shortest paths (SSP): repeatedly find the cheapest s→t path in the residual graph (by cost, not hop count), push the bottleneck flow, repeat until no path. Each augmentation is greedy-optimal, and the classic exchange argument shows the invariant holds: after each phase, the current flow is the cheapest flow of its value.

Johnson potentials: maintain π(v) = shortest-path distance from the last phase; reduced cost c(u,v) + π(u) − π(v) is provably ≥ 0 on all residual edges, so Dijkstra works from the second phase on (first phase needs Bellman-Ford, or all costs start non-negative). This is the fast version; SPFA-only is the simple version.

Assignment problems: unit capacities, bipartite shape — workers→slots with costs. This is Hungarian-algorithm territory (O(n³)), but MCMF is the programmable alternative: one reusable class solves assignment, transportation, and k-of-n selection problems with only graph-construction changes.

Interview Context

  • Codeforces / ICPC: standard; problems say “minimum total cost to satisfy demands”
  • Quant / operations-research-adjacent roles: real signal
  • LC 1066 Campus Bikes II (Hard, premium): the canonical LC assignment problem — intended answers are bitmask DP or MCMF
  • LC 2172 Maximum AND Sum (Hard): assignment in disguise (numbers→slots); bitmask DP expected, MCMF works
  • Standard FAANG: near zero as an implementation ask; occasionally as “how would you match drivers to riders optimally” design talk. Bitmask DP (phase-03 lab-08) covers the n ≤ 20 cases interviewers actually pose

When to Skip This Topic

Skip if any of these are true:

  • You haven’t done Dinic (lab-01) and bipartite matching (lab-02) — MCMF assumes residual-graph fluency
  • You’d reach for bitmask DP anyway and your targets keep n ≤ 20 (they do)
  • Bellman-Ford is hazy — SSP is Bellman-Ford in a loop

This is the last flow lab for a reason. Skip unless you’re contest-bound or genuinely done with everything else.

Problem Statement

Campus Bikes II (LC 1066).

Given n workers and m bikes (n ≤ m) on a 2D grid, assign each worker exactly one distinct bike minimizing the sum of Manhattan distances. Return the minimum sum.

General framing: minimum-cost perfect matching of workers into slots — the template for LC 2172 (numbers→slots maximizing AND sum: negate to minimize) and hire/delivery assignment problems.

Constraints

  • n ≤ m ≤ 10 on LC (bitmask DP works); the MCMF solution scales to n, m ≈ 500
  • 0 ≤ coordinates < 1000, so costs < 2000 per edge
  • Every worker must be assigned; bikes at most once

Clarifying Questions

  1. Must every worker get a bike? (Yes — maximize flow first, minimize cost among max flows.)
  2. Can two workers share a bike? (No — unit capacity on each bike.)
  3. Minimize total or worst-case distance? (Total. Min-max is a different problem: binary search + matching.)
  4. Costs ever negative? (Not here; in general MCMF handles them if there’s no negative cycle — SPFA covers it.)

Examples

workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]  → 6
(worker0→bike0: 3, worker1→bike1: 3)

workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]  → 4
(w0→b0: 1, w1→b1: 2, w2→b2: 1)

Greedy-nearest fails: two workers nearest to the same bike force a globally worse reassignment — exactly what the residual reverse edges repair.

Brute Force

Try all assignments: permutations of m bikes taken n at a time, m!/(m−n)! total. For n = m = 10: 3.6×10^6 — actually fine for LC 1066. For n = 20+: dead. Bitmask DP over bikes is O(n · 2^m); also dead past m ≈ 22.

Brute Force Complexity

  • Time: O(m!/(m−n)! · n) permutations; O(m · 2^m) bitmask DP
  • Space: O(n) / O(2^m)

Optimization Path

  1. Model as a flow network: source → each worker (cap 1, cost 0); worker i → bike j (cap 1, cost = Manhattan distance); each bike → sink (cap 1, cost 0).
  2. Max flow = n forces a complete assignment; min cost among max flows = optimal assignment.
  3. SSP: each phase, SPFA finds the cheapest augmenting path; push 1 unit; n phases total.
  4. Optional upgrade: keep potentials, switch to Dijkstra per phase — O(F · E log V) instead of O(F · V · E) worst case.

Final Expected Approach

from collections import deque
INF = float('inf')

class MCMF:
    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(n)]   # edge: [to, cap, cost, rev_index]

    def add_edge(self, u, v, cap, cost):
        self.g[u].append([v, cap, cost, len(self.g[v])])
        self.g[v].append([u, 0, -cost, len(self.g[u]) - 1])

    def min_cost_flow(self, s, t, want=INF):
        flow = cost = 0
        while flow < want:
            dist = [INF] * self.n
            in_q = [False] * self.n
            prev = [None] * self.n          # (node, index into g[node])
            dist[s] = 0
            q = deque([s])
            in_q[s] = True
            while q:                        # SPFA: Bellman-Ford with a queue
                u = q.popleft()
                in_q[u] = False
                for i, (v, cap, c, _) in enumerate(self.g[u]):
                    if cap > 0 and dist[u] + c < dist[v]:
                        dist[v] = dist[u] + c
                        prev[v] = (u, i)
                        if not in_q[v]:
                            q.append(v)
                            in_q[v] = True
            if dist[t] == INF:
                break                       # no augmenting path: done
            push = want - flow
            v = t
            while v != s:                   # bottleneck along parent chain
                u, i = prev[v]
                push = min(push, self.g[u][i][1])
                v = u
            v = t
            while v != s:                   # augment + open reverse edges
                u, i = prev[v]
                self.g[u][i][1] -= push
                self.g[v][self.g[u][i][3]][1] += push
                v = u
            flow += push
            cost += push * dist[t]
        return flow, cost

def assign_bikes(workers, bikes):           # LC 1066
    n, m = len(workers), len(bikes)
    S, T = n + m, n + m + 1
    net = MCMF(n + m + 2)
    for i in range(n):
        net.add_edge(S, i, 1, 0)
    for j in range(m):
        net.add_edge(n + j, T, 1, 0)
    for i, (wx, wy) in enumerate(workers):
        for j, (bx, by) in enumerate(bikes):
            net.add_edge(i, n + j, 1, abs(wx - bx) + abs(wy - by))
    return net.min_cost_flow(S, T)[1]

Data Structures

  • Adjacency list of edge records [to, cap, cost, rev_index]; reverse edge found in O(1) via rev_index
  • SPFA: deque + in-queue flags + dist array + parent (node, edge) pairs

Correctness Argument

  • Reverse edges with negated cost: rerouting flow off an edge refunds exactly what it cost — the residual graph encodes every possible modification of the current flow.
  • SSP invariant: if flow f is the min-cost flow of value |f|, augmenting along a shortest (cheapest) residual path yields the min-cost flow of the new value. Exchange argument: any cheaper flow of that value would imply a negative-cost cycle in the residual of f, contradicting f’s optimality.
  • No negative cycles initially (all costs ≥ 0) and SSP never creates one — so SPFA distances are well-defined at every phase.
  • Termination: each phase pushes ≥ 1 unit (integer capacities); at most F phases.

Complexity

  • SSP with SPFA: O(F · V · E) worst case; F ≤ n for unit-capacity assignment → O(n · V · E), and SPFA is near-linear on these sparse graphs in practice
  • Dijkstra + potentials: O(F · E log V)
  • Space: O(V + E); n = m = 500 → 250k assignment edges — fine

Implementation Requirements

  • Store the reverse-edge index at insertion; never search for it
  • SPFA needs in-queue flags (plain BFS relaxation is exponential on bad cases)
  • Parent must record (node, edge index), not just node — parallel edges are legal
  • Stop when dist[t] == INF, not when flow “looks” complete
  • want parameter: for k-of-n selection problems, cap total flow at k
  • Negated costs for maximization problems (LC 2172): maximize Σvalue = minimize Σ(−value)

Tests

  • LC 1066 example 1 → 6; example 2 → 4
  • Colinear stress: 5 workers on y=0, 5 bikes on y=999 → 5×999 (identity pairing among equals)
  • Two-path sanity: cheap low-cap path + expensive path — verify flow splits, cost = 10
  • Rerouting case where optimal flow must push back through a reverse edge (verify against hand-computed 10)
  • Stress: random n ≤ 4, m ≤ 5 grids vs brute-force permutations — 300 trials, exact equality
  • Edge case: n = 1 (picks the single nearest bike)

Follow-up Questions

  • Why not Dijkstra from the start? → Residual reverse edges have negative costs the moment any flow is pushed. Dijkstra’s greedy settling assumes no negative edges. Fix: Johnson potentials π(v) — reduced cost c + π(u) − π(v) ≥ 0 holds for all residual edges when π is the previous phase’s distance labels (edges on shortest paths get reduced cost exactly 0, and only those gain reverse edges). One initial Bellman-Ford (or zero, if costs start ≥ 0), then Dijkstra every phase.
  • Worst-case complexity and why it doesn’t bite here? → O(F) phases, each O(V·E) SPFA. F can be huge for big capacities (scaling MCMF or cost-scaling fixes that). For assignment, F ≤ n and per-phase graphs are small — n = 500 assignment runs in well under a second in C++.
  • When does the Hungarian algorithm win? → Dense square assignment with n in the thousands: Hungarian is O(n³) with tiny constants and no graph plumbing. MCMF wins on flexibility — unbalanced sides, capacities > 1, side constraints, k-of-n selection — with the same code.
  • What are the potentials, really? → LP dual variables. Min-cost flow’s dual assigns node prices; complementary slackness says flow travels only on edges whose reduced cost is 0. Johnson’s π is a feasible dual solution, and SSP is primal-dual: it maintains dual feasibility while growing the primal.
  • Minimize the maximum distance instead of the sum? → Different objective: binary search the threshold, keep only edges under it, check for perfect matching (lab-02). MCMF’s sum objective can’t express min-max directly.
  • Real deployments? → Ad-delivery pacing (impressions→campaigns under budgets), fulfillment-center-to-order matching at Amazon scale (solved as min-cost flow relaxations), ride-hailing driver dispatch, and kidney-exchange programs (cycle/chain variants built on the same machinery).

Product Extension

  • Rider-driver dispatch minimizing total ETA
  • Order-to-warehouse routing with per-warehouse capacity (cap > 1 on slot→sink edges — one-line change)
  • Ad impression allocation against advertiser budgets
  • On-call/shift scheduling with per-person load limits and preference costs

Language/Runtime Follow-ups

  • Python: fine to n ≈ 100 workers; list-based edge records beat Edge objects (attribute lookups dominate). PyPy or scipy.sparse.csgraph.min_cost_flow-style libraries for bigger.
  • C++: the contest standard; struct-of-arrays edges, std::deque SPFA, handles 10^5 edges easily.
  • Java: flatten edges into parallel int arrays; per-edge objects thrash GC.
  • Go: straightforward port; no surprises.

Common Bugs

  1. Missing or malformed reverse edge: cap 0 and cost −c are both mandatory; forgetting negation gives feasible flow with wrong (too high) cost — silently wrong, passes max-flow tests.
  2. Wrong rev_index: must be len(g[v]) before appending the reverse edge; off-by-one corrupts augmentation and caps go negative.
  3. Dijkstra on residual costs without potentials: works on the first phase, wrong afterward — the nastiest version passes small tests where no rerouting is needed.
  4. Parent-by-node instead of parent-by-edge: with parallel edges (two workers, same cost) you may decrement the wrong edge’s capacity.
  5. No in-queue flag in SPFA: correctness survives, runtime explodes — the same node is queued O(E) times.
  6. Augmenting before checking dist[t]: pushing along a stale parent chain when t was never reached; guard with the INF check.

Debugging Strategy

  • Assert the flow value equals n (all workers assigned) before trusting the cost
  • After termination, verify anti-symmetry: every edge pair satisfies cap_forward + cap_backward = original cap
  • Compare against brute-force permutations for n ≤ 4 — this catches cost bugs that max-flow tests can’t
  • Print each phase’s (dist[t], push): dist[t] must be non-decreasing across phases; a decrease means a negative cycle or a broken relaxation
  • Shrink failing stress cases by removing workers/bikes until minimal

Mastery Criteria

  • Write the MCMF class from memory in ≤ 35 min
  • Model LC 1066 as a flow network in ≤ 5 min (nodes, capacities, costs, why max-flow = assignment)
  • Explain why reverse-edge costs are negated and why Dijkstra needs potentials, without notes
  • State the SSP optimality invariant and sketch the exchange argument
  • Given an assignment problem, choose correctly between bitmask DP (n ≤ 20), MCMF, and Hungarian — and justify in one sentence each