Min-Cost Max-Flow Total Cost

Problem

Compute a maximum flow of minimum total cost with successive shortest augmenting paths.

Each round run Bellman-Ford on the residual graph with respect to cost, push the bottleneck along the cheapest s-t path, and accumulate flow times path cost. edges is a list of [u, v, capacity, cost] triples with distinct endpoint pairs. Return [max_flow, min_cost].

Hint

Bellman-Ford finds the cheapest residual path even when reverse edges carry negative cost.

Test cases

case 1

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

expected: [4,12]

case 2

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

expected: [3,15]

case 3

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

expected: [2,12]

case 4

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

expected: [0,0]

Starter codePython

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

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