Skip to main content
📜 WAYPOINT LESSON

Modeling Problems as Flow

⭐⭐⭐ advanced⏳ 35 min read📍 Lesson 155 of 281

Bipartite matching is source→left→right→sink with unit caps; node capacities split nodes; the modeling IS the algorithm choice.

Seeing networks everywhere

  • Bipartite matching: source→left (1), left→right per compatibility (1), right→sink (1). Max flow = max matching.
  • Node capacity c: split v into v_in→v_out cap c.
  • Multi-source/sink: super-source, super-sink.
  • Disjoint x-y paths: all caps 1 (vertex-disjoint: also split).

The exam skill is seeing capacity structure in word problems.

⚡ Now practice

Ready to Code
Flow TrioSmall max flow with cancellation, bipartite matching as flow, and Dinic on a layered load — greedy, no-augment, and unit-push wrongs.
3 challenges · · ~110 min