Min Cost Max Flow Problem

Min Cost Max Flow Problem — ExecCode Hard DSA Practice

Solve the Min Cost Max Flow problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Send as much flow as possible from source to sink on a directed network, and among all maximum flows choose one of minimum total cost. Unit bipartite assignment is Hungarian / Hopcroft–Karp; general graphs need Blossom for matching; blocking-flow max-flow is Dinic; push-relabel is the preflow alternative; min-cost is successive shortest paths on residual costs. Each edge is [u, v, capacity, cost] and may be used up to capacity times, adding cost per unit. Return [maxflow, mincost] for a cheapest maximum flow. If no residual path exists, max flow may be 0. You are given: n — node count, indices 0..n-1 edges — directed [u, v, cap, cost] source — source node sink — sink node Return [maxflow, mincost]. Anti-parallel residual edges are created by the algorithm, not given as input. Negative cycles are not present in the tests.

Examples

Input {'n': 4, 'edges': [[0, 1, 2, 1], [0, 2, 2, 2], [1, 3, 2, 1], [2, 3, 2, 1]], 'source': 0, 'sink': 3}; Output [4, 10]. Input {'n': 2, 'edges': [[0, 1, 5, 3]], 'source': 0, 'sink': 1}; Output [5, 15]. Input {'n': 3, 'edges': [[0, 1, 1, 10]], 'source': 0, 'sink': 2}; Output [0, 0]

Constraints

Capacities are non-negative Costs may be zero Parallel edges are allowed

Practice Min Cost Max Flow free on ExecCode. Browse DSA problems, topic map, and placement guides.