Most Water Through the Pipes
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
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
The second pipe lets only 3 through, however much arrives.
Example 3
The only pipe points the wrong way.
Constraints
2 <= n <= 90 <= len(pipes) <= 24, witha != band1 <= capacity <= 30source != sink
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- One Letter at a TimeHard
- Order of a Strange AlphabetHard
- Second Best TripHard
- Tour Every RoomHard
- Turn the SignpostsHard
- Use Every TicketHard
- Arrows In and OutBeginner
- Build the Neighbor ListsBeginner