Max-Flow Min-Cut Duality Check

Problem

Verify the max-flow min-cut theorem on a small network by computing both sides independently.

Run Ford-Fulkerson with DFS augmenting paths for the flow value, then take the capacity of the cut formed by nodes still reachable from s in the residual graph. Return True when the flow value and the cut capacity agree. edges is a list of [u, v, capacity] triples with integer capacities.

Hint

The residual reachable set always yields a cut whose capacity equals the flow.

Test cases

case 1

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

expected: true

case 2

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

expected: true

case 3

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

expected: true

case 4

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

expected: true

Starter codePython

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

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