Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 63 ยท Graphs for Contests

Maximum Flow and Matching in Contest Practice

A contest template for Dinic max flow in Python, then model bipartite matching, minimum cuts, vertex capacities and project selection, checked by brute force.

Flow problems rarely say "flow". They say "assign each student to a project with limited seats", "what is the smallest set of roads whose removal disconnects the city", or "choose projects to maximize profit, where some need others first". The skill that wins points is recognizing the flow model and building the graph correctly; the max-flow routine itself is a template you keep in your library.

This lesson gives you that template (Dinic's algorithm, written iteratively so Python's recursion limit never bites) and four modelling recipes: bipartite matching, minimum cut and finding the cut edges, vertex capacities by node splitting, and project selection (maximum closure). Each recipe is validated against a brute force. For the algorithm's theory see Network Flow and Push-Relabel and Min-Cost Flow.

The Dinic template

Dinic's algorithm repeats two phases:

  1. BFS from the source over edges with remaining capacity, to assign each node a level (distance in edges).
  2. Blocking flow: a DFS that only follows edges going from level l to level l + 1, with a current-arc pointer per node so no edge is scanned twice per phase. Repeat the DFS until no path is left.

Then rebuild levels and continue until the sink is unreachable. The complexity is O(V^2 E) in general, but much better on typical contest graphs: O(E sqrt(V)) for unit-capacity bipartite graphs.

Edges are stored in a pair of arrays, with edge e and its reverse e ^ 1.

Python Dinic's max flow (iterative), checked against brute-force min cut

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The brute force enumerates every way to split the nodes into a source side and a sink side: by the max-flow min-cut theorem the best cut equals the maximum flow, which gives us an independent check.

Recipe 1: bipartite matching

Left vertices on one side, right on the other, an edge for each allowed pair. Build:

  • source to each left vertex, capacity 1,
  • each left vertex to its right neighbors, capacity 1,
  • each right vertex to sink, capacity 1.

The max flow is the size of a maximum matching. For a capacity version ("project j has c_j seats"), put c_j on the right-to-sink edge. To recover the pairs, look at which left-to-right edges ended with zero residual capacity.

Python Bipartite matching with Dinic

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

By Konig's theorem, in a bipartite graph the size of a maximum matching equals the size of a minimum vertex cover, and the maximum independent set is V - matching. Many "pick the most items with no conflicts" problems are matching in disguise.

Recipe 2: minimum cut and which edges to cut

The max-flow value is the total capacity of a minimum cut. To list the cut edges: after the flow, find all nodes reachable from the source through edges with positive residual capacity. The cut consists of original edges going from a reachable node to an unreachable one. Use capacity INF for edges that must never be cut.

Vertex capacities and vertex-disjoint paths use node splitting: replace node v by v_in and v_out with an edge v_in -> v_out of capacity equal to the node's limit (1 for disjoint paths), and send incoming edges to v_in, outgoing edges from v_out.

Recipe 3: project selection (maximum closure)

You choose a subset of projects. Project i has a profit p_i (can be negative, a cost). If you take i you must also take every prerequisite of i. Maximize total profit.

Build a graph: source to each project with p_i > 0 (capacity p_i); each project with p_i < 0 to the sink (capacity -p_i); and an infinite edge from each project to each of its prerequisites. Then

TEXT
best profit = (sum of all positive profits) - (min cut)

The chosen set is the set of projects on the source side of the minimum cut.

Python Project selection via min cut, verified by subset enumeration

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same model solves "choose which machines to buy, given the jobs each enables" and many image-segmentation style problems (assign each pixel to foreground or background with pairwise penalties).

Recognizing flow problems

Statement says Model
Assign items to slots, each used at most once bipartite matching
Each slot or person has capacity c capacity c on the edge to the sink
"Minimum number to remove so A cannot reach B" min cut (edge or split-node capacities)
"Maximum number of paths with no shared edge or vertex" max flow with unit capacities, node splitting for vertices
Choose a set with dependencies to maximize profit project selection, positive - mincut
Choose items with no conflicting pairs, bipartite conflicts independent set = V - max matching

Common mistakes: forgetting the reverse edge with capacity 0, using too small an "infinite" capacity (use more than the sum of all finite capacities), creating the graph once per query instead of per test, and using recursive DFS on deep graphs.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How do you model maximum bipartite matching as a flow?

    Unit capacities on all three kinds of edges make each vertex used at most once; the flow value is the matching size.
  2. 2. How do you find which edges form a minimum cut after running max flow?

    Edges leaving the reachable set are saturated and form a cut whose capacity equals the max flow.
  3. 3. In project selection, what is the maximum profit?

    Start from taking every profitable project and subtract the cheapest set of profits lost or costs paid, which is exactly the min cut.
  4. 4. How do you limit how much flow can pass through a vertex v?

    Node splitting turns a vertex capacity into an ordinary edge capacity.

Summary

  • Keep an iterative Dinic template: BFS levels, DFS with current-arc pointers, reverse edges stored as e ^ 1.
  • Matching is flow with unit capacities; seats are capacities on the sink side. Konig: independent set = V minus maximum matching.
  • After max flow, nodes reachable from the source in the residual graph give the minimum cut.
  • Vertex capacities use node splitting; project selection gives sum of positive profits - min cut.
  • Verify models on tiny random inputs against brute force.

Next: SCC and 2-SAT for Contests