Maximum flow minimum cost
Your task
A directed network on n nodes (0..n-1) has edges [u, v, cap, cost] meaning a pipe from u to v with the given capacity and a per-unit cost. Send the MAXIMUM possible flow from s to t, and among all maximum-flow solutions pick one of minimum total cost. Return [max_flow_value, min_total_cost]. All costs are non-negative. Constraints: 1 <= n <= 200; 0 <= cap, cost <= 1000.
Examples
min_cost_max_flow(n: int, edges: list[list[int]], s: int, t: int) -> list[int]Example 1
Input
min_cost_max_flow(4, [[0, 1, 3, 1], [0, 2, 2, 2], [1, 3, 2, 1], [2, 3, 3, 1], [1, 2, 1, 1]], 0, 3)Output
[5, 13]