Capstone: Meridian's Dispatcher
In short: This section built four pieces — how much a network can carry, exactly which pipes are the reason it isn't more, a faster way to find the first number, and the cheapest way to move a fixed amount. The dispatcher puts the first two together into one end-of-shift report: run max flow, read the limiting cut straight out of the leftover residual graph, and price the cheapest pipe on that cut worth widening before tomorrow's shift. Nothing here is a new algorithm. It's the same residual graph, asked three questions instead of one.
Meridian's fixed shift roster
Two feeder docks, a shared hub, and a quieter side route through berth — four departures, two of them already pinched:
Widen costs, not shown here, ride along on each pipe for later. The run below only needs capacity.
Meridian's roster: two docks feed a shared hub, and dockB also has a quieter side route through berth. 6 nodes, 7 edges, directed. At depot.
Pulling the section together
Quick practice: reading the report
dispatched: 6 is the number ops cares about first thing in the morning.
cut_edges and cut_capacity are the number finance needs before they'll
approve anything: not "the network is slow," but "these two specific pipes
are the entire reason it's 6 and not more." cheapest_widen turns that
into a decision — of the two pipes actually worth touching, dockB-berth
at 4 beats hub-harbour at 6, so that's where the next rupee goes, and
lesson 2's widen_helps is the proof that spending it anywhere else
(depot-dockA, say) buys nothing at all.
# roster's cut: hub-harbour costs 6 to widen, dockB-berth costs 4
cut_widen_costs = [6, 4]
print(min(cut_widen_costs))What the whole section bought Meridian
| Lesson | Question | Answer for the roster |
|---|---|---|
| 1. Maximum Flow | How much, total? | 6 |
| 2. Min Cut & Duality | Which pipes, exactly? | dockB-berth, hub-harbour |
| 3. Faster Flow | How fast can I ask again? | Same answer, fewer BFS rounds |
| 4. Min-Cost Flow | What's the cheapest way to move less than the max? | Fill the cheap routes first |
| 5. Capstone | Put it together, then spend wisely | cheapest_widen: 4 |
❓ Cross-question: "If I widen dockB-berth by 1, does the max flow actually go up, or could the OTHER cut edge still cap it?" It goes up. Lesson 2 proved every cut edge is independently a bottleneck — widening one that's actually on the cut always raises the max flow by exactly 1, because the cut's capacity (the thing the max flow equals) went up by 1.
🎯 Your turn
Write dispatch_plan(routes, source, sink). routes is
[from, to, capacity, widen_cost]. Run max flow, find the cut in the final
residual graph, and report the cheapest cut edge to widen:
dispatch_plan([["s", "a", 3, 2], ["a", "t", 2, 5]], "s", "t")→{"dispatched": 2, "cut_edges": [["a", "t"]], "cut_capacity": 2, "cheapest_widen": 5}
Hint: this is lessons 1 and 2, run back to back, with a
{(from, to): widen_cost} lookup built once at the start.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = Meridian's dispatcher is fully built. ✅