Max Flow with Vertex Capacities

Problem

Compute the maximum flow from s to t in a directed graph where every vertex has a capacity.

Split each vertex v into v_in and v_out joined by an edge of capacity capacities[v]; source and sink get unlimited capacity. Each original edge u to v becomes an unlimited edge from u_out to v_in. Run Ford-Fulkerson on the split network with large finite capacities. edges is a list of [u, v] pairs.

Hint

Node splitting turns a vertex capacity into a single edge capacity.

Test cases

case 1

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

expected: 3

case 2

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

expected: 1

case 3

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

expected: 20

case 4

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

expected: 4

case 5

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

expected: 0

Starter codePython

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

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