The most trains

Return the value of a maximum flow from s to t: the most trains an hour that can leave s and reach t, keeping both rules of P1.

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)]
max_flow(6, lines, 0, 5)      # 19
max_flow(4, [(0, 1, 1), (0, 2, 1), (1, 2, 1),
             (1, 3, 1), (2, 3, 1)], 0, 3)   # 2

In the second network, the path 0 → 1 → 2 → 3 sends one train, and then no path is left in the network itself. The residual graph of lesson 2 still has a path, because it can undo the train on 1 → 2.

Limits

• Up to 50 stations and 300 lines, capacities up to 100. Any augmenting-path method is fast enough.