Pipe Network Flow

A water network has n junctions, numbered 0 to n - 1. Each pipe [a, b, capacity] in pipes carries water one way, from junction a to junction b, at most capacity litres per second. Water enters the network at the junction source and leaves it at the junction sink. At every other junction exactly as much water must flow out as flows in.

Write max_flow(n, pipes, source, sink) that returns the largest number of litres per second that can flow from source to sink.

Examples

max_flow(4, [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]], 0, 3)  # returns 5
max_flow(4, [[0, 1, 1], [0, 2, 1], [1, 2, 1], [1, 3, 1], [2, 3, 1]], 0, 3)  # returns 2
max_flow(3, [[0, 1, 5], [2, 1, 5]], 0, 2)  # returns 0

In the second network, sending one litre along 0, 1, 2, 3 first seems to block everything else, yet one litre along 0, 1, 3 and one along 0, 2, 3 gets 2 litres through. A method that only ever adds water to the best-looking route can get stuck, so it must be able to take back earlier choices.

Constraints

• 2 <= n <= 1,000, with up to 5,000 pipes, and source and sink are different junctions.
• Capacities are integers from 0 to 1,000,000. Pipes can run both ways between two junctions, and two junctions can be joined by several pipes.