The problem
Now return the plan itself: a pair (value, flow), where flow[i] is the number of trains an hour on line i in a maximum flow. Any maximum flow is accepted: the tests check your flow line by line (both rules of P1) and its value.
lines = [(0, 1, 10), (0, 2, 10), (1, 2, 2),
(1, 3, 4), (1, 4, 8), (2, 4, 9),
(4, 3, 6), (3, 5, 10), (4, 5, 10)]
flow_plan(6, lines, 0, 5)
# (19, [10, 9, 0, 4, 6, 9, 5, 9, 10])
The flow on line i is what its reverse arc holds at the end: the trains sent along it minus the trains sent back. Capacities are whole numbers up to 10⁹ (1,000,000,000).
Limits
- Up to 10,000 stations and 50,000 lines. The big tests have 4 to 5 seconds each.
- Paths found by depth-first search can carry very little each, so plain Ford-Fulkerson is too slow. Edmonds-Karp passes every test but the last.
- The last test has 160 layers of stations; it needs Dinic’s method (lesson 3).
Builds on FLOW-3 Edmonds-Karp and Dinic.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | The diamond | Not run | |
| 3 | Nothing to send | Not run | |
| 4 | Two ways round | Not run | |
| 5 | 2,000 stations, large capacities | Not run | |
| 6 | 10,000 stations, capacities up to 10⁹ | Not run | |
| 7 | 160 layers of 30 | Not run |