Maximum Flow Through Pipes
- Memory limit
- 256 MB
- Correctness time limit
- 20000 ms
- Solvers
- 0
n water facilities (0..n-1) are linked by one-way pipes; edges[i] = [u, v, c] carries up to c tons per second from
u to v (parallel pipes and opposite-direction pipes may exist). Water leaves source and is collected at sink; nothing is
stored or lost at intermediate facilities. Return the maximum amount per second that can reach sink.
Examples
| n | edges | source | sink | result |
|---|---|---|---|---|
4 | [[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]] | 0 | 3 | 5 |
3 | [[0, 1, 5], [2, 1, 5]] | 0 | 2 | 0 |
4 | [[0, 1, 1000000000], [1, 2, 1], [0, 2, 1000000000], [1, 3, 1000000000], [2, 3, 1000000000]] | 0 | 3 | 2000000000 |
Example 1 — 2 along 0→1→3, 2 along 0→2→3, 1 along 0→1→2→3; the pipes leaving 0 allow no more.
Example 2 — the pipe 2 → 1 points the wrong way.
Example 3 — the answer may not fit in 32 bits.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(n: int, edges: int[][], source: int, sink: int) → long
Constraints
-
n -
edges.length edges[i] = [u, v, c],n, ,-
source,sinkn,sourcesink - The answer may not fit in 32 bits.
Expected complexity
- Time
- O(V^2 E) worst case, O(E sqrt(V)) on unit networks (Dinic)
- Space
- O(V + E)
Examples
| n | edges | source | sink | Expected |
|---|---|---|---|---|
4 | [[0,1,3],[0,2,2],[1,2,5],[1,3,2],[2,3,3]] | 0 | 3 | 5 |
3 | [[0,1,5],[2,1,5]] | 0 | 2 | 0 |
4 | [[0,1,1000000000],[1,2,1],[0,2,1000000000],[1,3,1000000000],[2,3,1000000000]] | 0 | 3 | 2000000000 |
Hint
Hint
Work on the residual graph (remaining capacity plus a reverse edge for every pipe so flow can be cancelled) and use Dinic's
algorithm: BFS from source to compute levels, then push a blocking flow with DFS along edges that go exactly one level
deeper, keeping a per-vertex "next edge" pointer so dead edges are never scanned twice; repeat until sink is unreachable.
Use 64-bit totals. Edmonds-Karp (a full BFS for every augmenting path) exceeds the time limit on the performance tests.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 518 ms | estimated |
| C++ (GCC, gnu++23) | 518 ms | derived |
| Python 3.13 | 7048 ms | derived |
| Java 25 | 2038 ms | derived |
| Kotlin 2.4 (JVM) | 2036 ms | estimated |
| C# 14 (.NET 10) | 2036 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 5 | verdict only |