The weakest set of lines

A cut splits the stations into a side S that holds s and the rest, which holds t. Its capacity is the total capacity of the lines from S to the rest; lines the other way do not count. Return a side S whose cut has the smallest capacity: the cheapest set of lines to close so that no train can get from s to t.

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)]
min_cut(6, lines, 0, 5)   # [0, 2]: it cuts the lines
                          # 0 -> 1 and 2 -> 4, 10 + 9 = 19

When several sides give the least capacity, any of them is accepted: the tests check that your side holds s and not t, and add up its cut.

Limits

• Up to 10,000 stations and 50,000 lines, capacities up to 10⁹. The big tests have 4 seconds each.