Min Cut Value from Max Flow

Problem

Compute a minimum s-t cut from a maximum flow, using the max-flow min-cut theorem.

Run Ford-Fulkerson with DFS augmenting paths, then find all nodes reachable from s in the residual network. Return [cut_value, source_side] where source_side is the sorted list of reachable nodes. edges is a list of [u, v, capacity] triples.

Hint

After no augmenting path remains, nodes reachable from s in the residual graph form the source side of a min cut.

Test cases

case 1

in: [4,[[0,1,3],[0,2,2],[1,2,5],[1,3,2],[2,3,3]],0,3]

expected: [5,[0]]

case 2

in: [3,[[0,1,1],[1,2,1]],0,2]

expected: [1,[0]]

case 3

in: [3,[[0,1,5]],0,2]

expected: [0,[0,1]]

case 4

in: [4,[[0,1,10],[0,2,10],[1,2,1],[1,3,10],[2,3,10]],0,3]

expected: [20,[0]]

Starter codePython

def min_cut(n, edges, s, t):
    # Your code here
    pass

4 test cases · run your code against them in the editor