1080. Max Flow — Ford-Fulkerson Algorithm

Given a directed flow network with n nodes and edges [u, v, cap] (capacity cap), a source, and a sink, return the maximum flow from source to sink using the Ford-Fulkerson method (DFS augmenting paths). The input is JSON {n, edges, source, sink}.

Input: JSON {n, edges, source, sink} with edges [u, v, cap].

Output: Integer — the maximum flow value.

Examples

Input: {"n":4,"edges":[[0,1,3],[0,2,2],[1,2,1],[1,3,2],[2,3,3]],"source":0,"sink":3}
Output: 5
Explanation: Maximum flow is 5.

Input: {"n":2,"edges":[[0,1,5]],"source":0,"sink":1}
Output: 5
Explanation: Single edge capacity.

Input: {"n":3,"edges":[[0,1,4],[1,2,3]],"source":0,"sink":2}
Output: 3
Explanation: Bottleneck of 3.

Constraints

• 1<=n<=200
• cap>=1
• directed

Asked by