1082. Minimum Cut in a Flow Network

Given a directed flow network with n nodes and edges [u, v, cap], a source, and a sink, return the value of the minimum s-t cut — the smallest total capacity of edges whose removal disconnects source from sink. By the max-flow min-cut theorem this equals the maximum flow. The input is JSON {n, edges, source, sink}.

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

Output: Integer — the minimum cut 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: Min cut equals max flow 5.

Input: {"n":2,"edges":[[0,1,5]],"source":0,"sink":1}
Output: 5
Explanation: The single edge is the cut.

Input: {"n":3,"edges":[[0,1,4],[1,2,3]],"source":0,"sink":2}
Output: 3
Explanation: Cut at the bottleneck.

Constraints

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

Asked by