Flow with Demands Feasibility Lite

Problem

Decide whether a directed capacitated network can route all supplies to all demands.

supplies[i] is positive for producers, negative for consumers, and must sum to 0. Connect a super source to producers and consumers to a super sink, then check whether the max flow saturates all supply. edges is a list of [u, v, capacity] triples. Return a boolean.

Hint

Demand feasibility is max flow with a super source and a super sink.

Test cases

case 1

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

expected: true

case 2

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

expected: false

case 3

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

expected: true

case 4

in: [2,[],[1,-1]]

expected: false

Starter codePython

def flow_demands_feasible(n, edges, supplies):
    # Your code here
    pass

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