FunctionRacerProblemsRace

Most Water Through the Pipes

HardGraphsPython, JavaScript, TypeScript, Java, C++

A waterworks has n junctions numbered 0 to n - 1. Each entry of pipes is [a, b, capacity]: a pipe that carries water from junction a to junction b, in that direction only, at up to capacity litres a second. Several pipes may join the same two junctions.

Water enters at source and leaves at sink. At every other junction as much flows out as flows in, and no pipe carries more than its capacity.

Return the largest number of litres a second that can reach the sink.

Example 1

n 4
pipes [[0,1,3],[0,2,2],[1,3,2],[2,3,3],[1,2,1]]
source 0
sink 3
returns 5

Two litres go 0, 1, 3 and two go 0, 2, 3. One more goes 0, 1, 2, 3, which fills both pipes into the sink.

Example 2

n 3
pipes [[0,1,5],[1,2,3]]
source 0
sink 2
returns 3

The second pipe lets only 3 through, however much arrives.

Example 3

n 2
pipes [[1,0,4]]
source 0
sink 1
returns 0

The only pipe points the wrong way.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems