Recipe

Model and solve a transportation or matching problem

Use when: you see two groups connected by capacity-limited connections, whether it's an exact one-to-one pairing or supplies and demands larger than one unit

Goal: a maximum flow value and a routing that shows exactly how many units move along every connection

Taught in Matching and flow in practice

1. 1

   List how much each left vertex can supply, how much each right vertex needs, and the capacity of every connecting edge between them.

   Example

   Two warehouses and two stores: w_A supplies 3, w_B supplies 2; s_X needs 2, s_Y needs 3; every lane between a warehouse and a store carries up to 2.

   Why: every later step works only from these numbers, so getting them right first avoids rebuilding the network later.

2. 2

   Add a source s with an edge into each left vertex capped at its supply, and a sink t with an edge out of each right vertex capped at its demand.

   Example

   s\to w_A gets capacity 3 and s\to w_B gets capacity 2; s_X\to t gets capacity 2 and s_Y\to t gets capacity 3.

   • general supply and demand values above 1 — keep the original numbers on every edge.
   • plain one-to-one matching, one worker per job — force every supply, demand, and lane capacity down to 1.

   Why: capping the source and sink edges is what turns a scattered set of per-vertex limits into one single max-flow question.

3. 3

   Push flow along augmenting paths from s to t, exactly as Sections 1 through 5's Ford-Fulkerson method does, until none remain.

   Example

   Path s\to w_A\to s_X\to t pushes 2; path s\to w_A\to s_Y\to t pushes 1; path s\to w_B\to s_Y\to t pushes 2; total flow 5.

   ⚡ Shortcut

   When every capacity in the network is already 1, as in plain matching, each augmenting path found has bottleneck 1, so it adds exactly one matched pair.

   Why: nothing about the algorithm itself changes between transportation and matching; only the numbers written on the edges differ.

4. 4

   Compare the max-flow value to total supply and total demand, then check each used edge for how many units it actually carries.

   Example

   Max flow 5 equals both total supply and total demand, so w_A ships 2 to s_X and 1 to s_Y, while w_B ships 2 to s_Y.

   • max flow equals total supply and total demand — every unit is delivered, or every left vertex is matched.
   • max flow falls short of total supply or total demand — some supply is stranded, or a full matching is impossible.

   Why: max-flow min-cut guarantees this value is the largest any network of these capacities could ever carry, so a shortfall is a genuine limit, not a solving error.