P32 · 2 seconds · 256 MB
Download Speed
`cap` is an `n×n` capacity matrix (`cap[u][v]` is the capacity of the directed edge u→v; 0 means no edge). Return the maximum flow from `s` to `t`. If `s === t`, return `0`. Capacities are non-negative integers.
function maxFlow(cap, s, t) → number
CONSTRAINTS
- 1 ≤ n ≤ 12
- cap is n×n
- 0 ≤ cap[u][v] ≤ 1000
- 0 ≤ s, t < n
Input: cap = [[0,2,2,0],[0,0,1,1],[0,0,0,2],[0,0,0,0]], s = 0, t = 3
Output: 3
Input: cap = [[0,5],[0,0]], s = 0, t = 1
Output: 5
1
2
3
4
5
6
7
8
Arena judges JavaScript in a Web Worker (1s wall-clock, then TLE). Samples are public; submit runs hidden tests too. C++/Python is a later swarm package.