Min-Cut Capacity by Enumeration

Problem

Find the minimum s-t cut capacity by enumerating every vertex subset.

For each subset S containing s but not t, sum the capacities of directed edges from S to the complement, and return the smallest total. edges is a list of [u, v, capacity] triples and n is small so 2^n subsets are affordable. If s equals t return 0.

Hint

A cut is fully described by which nodes stay on the source side.

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

case 2

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

expected: 1

case 3

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

expected: 0

case 4

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

expected: 4

case 5

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

expected: 0

Starter codePython

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

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