Minimum Cost Maximum Flow (MCMF)

Problem Overview

Learning Goals

After studying this algorithm, you will be able to:

• Understand the relationship between maximum flow and minimum cost
• Implement SPFA-based shortest path finding with negative edge costs
• Model assignment and transportation problems as MCMF
• Handle negative costs correctly in flow networks
• Compare and choose between standard max flow and MCMF

Problem Statement

Problem: Given a directed graph where each edge has both a capacity and a cost per unit flow, find the maximum flow from source to sink while minimizing the total cost.

Input:

• Line 1: n m (number of nodes, number of edges)
• Lines 2 to m+1: u v cap cost (edge from u to v with capacity and cost per unit)
• Source is node 1, Sink is node n

Output:

• Two integers: maximum flow and minimum total cost

Constraints:

• 1 <= n <= 5000
• 1 <= m <= 50000
• 0 <= cap <= 10^9
• -10^4 <= cost <= 10^4

Example

Input:
4 5
1 2 2 1
1 3 1 4
2 3 1 2
2 4 1 3
3 4 2 1

Output:
2 8

Explanation: Maximum flow of 2 achieved with paths: 1->2->4 (flow=1, cost=4) and 1->3->4 (flow=1, cost=5). Total cost = 4 + 5 = 9. Alternative: 1->2->3->4 gives lower cost.

Intuition: How to Think About This Problem

Pattern Recognition

Key Question: How do we combine the goals of maximizing flow AND minimizing cost?

Standard max flow ignores costs and only cares about pushing maximum units. MCMF adds an optimization layer: among all ways to achieve max flow, find the cheapest one.

Breaking Down the Problem

1. What are we looking for? Maximum flow with minimum total cost
2. What information do we have? Capacities AND costs on each edge
3. What is the key insight? Repeatedly find the cheapest augmenting path

The Core Idea

Instead of using BFS (like Edmonds-Karp) to find any augmenting path, we use shortest path algorithms to find the minimum cost augmenting path. By always augmenting along the cheapest path first, we guarantee minimum total cost.

Algorithm: Successive Shortest Paths

Why SPFA/Bellman-Ford?

We cannot use Dijkstra directly because:

1. Residual edges have negative costs (reverse of original cost)
2. Original edges may have negative costs

SPFA (Shortest Path Faster Algorithm) handles negative edges efficiently.

Algorithm Steps

1. Initialize: Create residual graph with forward and backward edges
2. Find Path: Use SPFA from source to sink to find minimum cost path
3. Augment: Push maximum possible flow along this path
4. Update Cost: Add (flow * path_cost) to total cost
5. Repeat: Continue until no augmenting path exists

SPFA Overview

SPFA is a queue-based optimization of Bellman-Ford:

• Maintain a queue of nodes to process
• Only add a node to queue if its distance improves
• Average case: O(k * E) where k is small constant

SPFA(source, sink):
    dist[all] = INF, dist[source] = 0
    queue = [source], in_queue[source] = true

    while queue not empty:
        u = queue.pop_front()
        in_queue[u] = false
        for each edge (u -> v) with remaining capacity:
            if dist[u] + cost(u,v) < dist[v]:
                dist[v] = dist[u] + cost(u,v)
                parent[v] = u
                if v not in queue:
                    queue.push_back(v)
                    in_queue[v] = true

    return dist[sink] != INF

Dry Run Example

Network Setup

Nodes: 4 (Source=1, Sink=4)
Edges (u->v, cap, cost):
  1->2: cap=2, cost=1
  1->3: cap=1, cost=4
  2->3: cap=1, cost=2
  2->4: cap=1, cost=3
  3->4: cap=2, cost=1

     [1]----cap=2,cost=1---->[2]
      |                       |  \
 cap=1|                  cap=1|   \cap=1,cost=3
cost=4|                 cost=2|    \
      v                       v     v
     [3]<------------------  [2]   [4]
      |                             ^
      +------cap=2,cost=1----------+

Iteration 1: Find Shortest Path

SPFA from node 1:
  dist = [0, INF, INF, INF]

  Process node 1:
    Edge 1->2: dist[2] = 0 + 1 = 1
    Edge 1->3: dist[3] = 0 + 4 = 4
  dist = [0, 1, 4, INF]

  Process node 2:
    Edge 2->3: dist[3] = min(4, 1+2) = 3
    Edge 2->4: dist[4] = 1 + 3 = 4
  dist = [0, 1, 3, 4]

  Process node 3:
    Edge 3->4: dist[4] = min(4, 3+1) = 4
  dist = [0, 1, 3, 4]

Shortest path: 1 -> 2 -> 4, cost = 4
Bottleneck capacity = min(2, 1) = 1
Flow += 1, Total Cost += 1 * 4 = 4

Iteration 2: Update Residual Graph and Find Next Path

Updated capacities:
  1->2: cap=1 (was 2)
  2->4: cap=0 (was 1)
  Reverse edges: 2->1: cap=1, 4->2: cap=1

SPFA from node 1:
  Shortest path: 1 -> 2 -> 3 -> 4, cost = 1+2+1 = 4
  Bottleneck = min(1, 1, 2) = 1
  Flow += 1, Total Cost += 1 * 4 = 4

Total: Flow = 2, Cost = 8

Iteration 3: No More Paths

After iteration 2:
  1->2: cap=0, 1->3: cap=1
  Path 1->3->4 has cost 4+1=5

  Shortest path: 1 -> 3 -> 4, cost = 5
  But wait - can we do better with residual edges?

  Actually, 2->4 is saturated, so no path through node 2.
  Only path: 1->3->4 but capacity=1 already used? No, cap=1 remains.

Final augment: 1->3->4, flow=1? No - we already have max flow=2.
Check: source outgoing = 2+1=3, but paths found use 2.

Final Answer: Max Flow = 2, Min Cost = 8

Common Mistakes

Mistake 1: Using Dijkstra with Negative Costs

Problem: Dijkstra assumes no negative edges. Residual edges have -cost. Fix: Use SPFA or Bellman-Ford instead.

Mistake 2: Forgetting Reverse Edge Costs

Problem: Canceling flow should refund the cost. Fix: Reverse edge cost = -original_cost.

Mistake 3: Not Detecting Negative Cycles

Problem: Negative cost cycles can be exploited infinitely. Fix: Check for negative cycles or use potential function (Johnson’s technique).

Mistake 4: Integer Overflow in Cost Calculation

Fix: Use long long for cost accumulation.

Edge Cases

When to Use MCMF

Use This Approach When:

• Assignment Problems: Assign n workers to n jobs with costs
• Transportation Problems: Ship goods from warehouses to stores
• Bipartite Matching with Weights: Find min/max weight perfect matching
• Resource Allocation: Distribute resources with associated costs
• Network Design: Route traffic minimizing total latency

Do Not Use When:

• Only maximum flow needed (no costs) - use simpler max flow
• Costs are all equal - reduces to standard max flow
• Graph is too large (>10^4 nodes) - may be too slow
• Need online/dynamic updates - MCMF is batch-only

Pattern Recognition Checklist

• Need both maximum throughput AND minimum cost? --> MCMF
• Assignment with preferences/costs? --> MCMF
• Bipartite matching with weights? --> MCMF or Hungarian
• Just need max flow? --> Dinic/Edmonds-Karp

Comparison: Max Flow vs MCMF

Solution: Python Implementation

from collections import deque

class MCMF:
  def __init__(self, n):
    self.n = n
    self.graph = [[] for _ in range(n)]

  def add_edge(self, u, v, cap, cost):
    """Add edge u->v with capacity and cost per unit."""
    # Forward edge: capacity=cap, cost=cost
    # Backward edge: capacity=0, cost=-cost
    self.graph[u].append([v, cap, cost, len(self.graph[v])])
    self.graph[v].append([u, 0, -cost, len(self.graph[u]) - 1])

  def spfa(self, source, sink, dist, parent, parent_edge):
    """Find shortest path using SPFA. Returns True if path exists."""
    INF = float('inf')
    dist[:] = [INF] * self.n
    dist[source] = 0
    in_queue = [False] * self.n
    in_queue[source] = True
    queue = deque([source])

    while queue:
      u = queue.popleft()
      in_queue[u] = False

      for i, (v, cap, cost, _) in enumerate(self.graph[u]):
        if cap > 0 and dist[u] + cost < dist[v]:
          dist[v] = dist[u] + cost
          parent[v] = u
          parent_edge[v] = i
          if not in_queue[v]:
            queue.append(v)
            in_queue[v] = True

    return dist[sink] != INF

  def min_cost_max_flow(self, source, sink):
    """Returns (max_flow, min_cost)."""
    max_flow = 0
    min_cost = 0
    dist = [0] * self.n
    parent = [-1] * self.n
    parent_edge = [-1] * self.n

    while self.spfa(source, sink, dist, parent, parent_edge):
      # Find bottleneck capacity
      flow = float('inf')
      v = sink
      while v != source:
        u = parent[v]
        edge_idx = parent_edge[v]
        flow = min(flow, self.graph[u][edge_idx][1])
        v = u

      # Update flow along path
      v = sink
      while v != source:
        u = parent[v]
        edge_idx = parent_edge[v]
        rev_idx = self.graph[u][edge_idx][3]
        self.graph[u][edge_idx][1] -= flow
        self.graph[v][rev_idx][1] += flow
        v = u

      max_flow += flow
      min_cost += flow * dist[sink]

    return max_flow, min_cost


def solve():
  n, m = map(int, input().split())
  mcmf = MCMF(n)

  for _ in range(m):
    u, v, cap, cost = map(int, input().split())
    mcmf.add_edge(u - 1, v - 1, cap, cost)  # 0-indexed

  flow, cost = mcmf.min_cost_max_flow(0, n - 1)
  print(flow, cost)


if __name__ == "__main__":
  solve()

Complexity Analysis

Note: With Johnson’s potential optimization, complexity improves to O(V * E * log(V) * F) using Dijkstra after initial Bellman-Ford.

Related Problems

Prerequisites (Do These First)

CSES Applications

Harder (Do These After)

Key Takeaways

1. Core Idea: Always augment along minimum cost path to guarantee optimal cost
2. Path Finding: Use SPFA/Bellman-Ford to handle negative edge costs
3. Reverse Edges: Cost of reverse edge must be negative of forward edge
4. Applications: Assignment problems, transportation, weighted matching
5. Trade-off: More complex than standard max flow, but solves optimization variant

Practice Checklist

Before moving on, make sure you can:

• Implement MCMF with SPFA from scratch
• Explain why Dijkstra fails with residual graphs
• Model an assignment problem as MCMF
• Debug common issues (negative cycles, cost overflow)
• Know when to use MCMF vs standard max flow