Funcia
Lv.4dinicgraphmax-flow

Maximum Flow Through Pipes

Memory limit
256 MB
Correctness time limit
20000 ms
Solvers
0
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

nedgessourcesinkresult
4[[0, 1, 3], [0, 2, 2], [1, 2, 5], [1, 3, 2], [2, 3, 3]]035
3[[0, 1, 5], [2, 1, 5]]020
4[[0, 1, 1000000000], [1, 2, 1], [0, 2, 1000000000], [1, 3, 1000000000], [2, 3, 1000000000]]032000000000

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

  • 2≤2 \le n ≤10,000\le 10{,}000
  • 0≤0 \le edges.length ≤100,000\le 100{,}000
  • edges[i] = [u, v, c], 0≤u,v<0 \le u, v < n, u≠vu \ne v, 1≤c≤1091 \le c \le 10^9
  • 0≤0 \le source, sink << n, source ≠\ne sink
  • 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

nedgessourcesinkExpected
4[[0,1,3],[0,2,2],[1,2,5],[1,3,2],[2,3,3]]035
3[[0,1,5],[2,1,5]]020
4[[0,1,1000000000],[1,2,1],[0,2,1000000000],[1,3,1000000000],[2,3,1000000000]]032000000000

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

LanguageEfficiency time limit
C (GCC, gnu17)518 msestimated
C++ (GCC, gnu++23)518 msderived
Python 3.137048 msderived
Java 252038 msderived
Kotlin 2.4 (JVM)2036 msestimated
C# 14 (.NET 10)2036 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance605verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.