PreviousNext
Coding/Graphs and trees

Feasible circulation

Write codeHard50 min

Your task

You are given a directed graph on n nodes (0..n-1). Each edge is [u, v, low, high]: a flow on that edge must be an integer in [low, high]. Decide whether a feasible circulation exists - an assignment of flow to every edge satisfying its [low, high] bound AND flow conservation at EVERY node (total in == total out, no source or sink). Return true if feasible, else false. Constraints: 1 <= n <= 200; 0 <= low <= high <= 1000.

Examples

feasible_circulation(n: int, edges: list[list[int]]) -> bool
Example 1
Inputfeasible_circulation(3, [[0, 1, 1, 3], [1, 2, 1, 3], [2, 0, 1, 3]])
OutputTrue