1081. Max Flow — Edmonds-Karp (BFS-based)

Given a directed flow network with n nodes and edges [u, v, cap], a source, and a sink, return the maximum flow using the Edmonds-Karp algorithm (BFS to find shortest 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: Same maximum flow of 5.

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

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