Minimum cost maximum flow
Given a directed graph with n nodes (0..n-1) and edges [u, v, cap, cost] (per-unit cost, non-negative capacity), find the maximum flow from source s to sink t and, among all max flows, the minimum total cost. Return a two-element list [max_flow, min_cost]. Costs are non-negative integers. If t is unreachable return [0, 0]. Assume 1 <= n <= 200 with small capacities so successive shortest augmenting paths finish under 5s.
Implement
min_cost_max_flow(n: int, edges: list[list[int]], s: int, t: int) → list[int]Examples
in
[4,[[0,1,2,1],[0,2,1,2],[1,3,1,1],[2,3,2,1],[1,2,1,1]],0,3]out[3,8]What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 45 min
solution.py
InputExpectedGot
[4,[[0,1,2,1],[0,2,1,2],[1,3,1,1],[2,3,2,1],[1,2,1,1]],0,3][3,8]not run yetsample