Min Cost Max Flow (MCMF)

Minimum Cost Maximum Flow finds a flow of maximum value with the minimum total cost in a flow network.

Problem Definition

• Each edge has a capacity $c(u,v)$ and a cost $w(u,v)$.
• The cost of a flow $f$ is $\sum f(u,v) \cdot w(u,v)$.
• Find the maximum flow from source to sink with the minimum total cost.

SPFA-based MCMF

Uses SPFA (Shortest Path Faster Algorithm) to find shortest paths in the residual graph.

Implementation

struct MCMF {
    struct Edge {
        int to, rev;
        long long cap, cost;
    };
    int n;
    vector<vector<Edge>> graph;
    vector<long long> dist;
    vector<int> prevv, preve;
    vector<bool> inQueue;
    MCMF(int n) : n(n), graph(n), dist(n), prevv(n), preve(n), inQueue(n) {}
    void addEdge(int from, int to, long long cap, long long cost) {
        graph[from].push_back({to, (int)graph[to].size(), cap, cost});
        graph[to].push_back({from, (int)graph[from].size() - 1, 0, -cost});
    }
    bool spfa(int s, int t) {
        fill(dist.begin(), dist.end(), LLONG_MAX);
        fill(inQueue.begin(), inQueue.end(), false);
        queue<int> q;
        dist[s] = 0;
        q.push(s);
        inQueue[s] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            inQueue[u] = false;
            for (int i = 0; i < graph[u].size(); i++) {
                Edge& e = graph[u][i];
                if (e.cap > 0 && dist[u] + e.cost < dist[e.to]) {
                    dist[e.to] = dist[u] + e.cost;
                    prevv[e.to] = u;
                    preve[e.to] = i;
                    if (!inQueue[e.to]) {
                        q.push(e.to);
                        inQueue[e.to] = true;
                    }
                }
            }
        }
        return dist[t] != LLONG_MAX;
    }
    pair<long long, long long> minCostMaxFlow(int s, int t, long long maxFlow = LLONG_MAX) {
        long long flow = 0, cost = 0;
        while (flow < maxFlow && spfa(s, t)) {
            long long d = maxFlow - flow;
            for (int v = t; v != s; v = prevv[v]) {
                d = min(d, graph[prevv[v]][preve[v]].cap);
            }
            for (int v = t; v != s; v = prevv[v]) {
                Edge& e = graph[prevv[v]][preve[v]];
                e.cap -= d;
                graph[v][e.rev].cap += d;
            }
            flow += d;
            cost += d * dist[t];
        }
        return {flow, cost};
    }
};

Dijkstra-based MCMF (with Potentials)

Uses Dijkstra’s algorithm with Johnson’s potentials to handle negative edges efficiently.

struct MCMF_Dijkstra {
    struct Edge {
        int to, rev;
        long long cap, cost;
    };
    int n;
    vector<vector<Edge>> graph;
    vector<long long> h;  // potential
    vector<long long> dist;
    vector<int> prevv, preve;
    MCMF_Dijkstra(int n) : n(n), graph(n), h(n), dist(n), prevv(n), preve(n) {}
    void addEdge(int from, int to, long long cap, long long cost) {
        graph[from].push_back({to, (int)graph[to].size(), cap, cost});
        graph[to].push_back({from, (int)graph[from].size() - 1, 0, -cost});
    }
    pair<long long, long long> minCostMaxFlow(int s, int t, long long maxFlow = LLONG_MAX) {
        long long flow = 0, cost = 0;
        fill(h.begin(), h.end(), 0);
        while (flow < maxFlow) {
            fill(dist.begin(), dist.end(), LLONG_MAX);
            priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
            dist[s] = 0;
            pq.push({0, s});
            while (!pq.empty()) {
                auto [d, u] = pq.top(); pq.pop();
                if (d > dist[u]) continue;
                for (int i = 0; i < graph[u].size(); i++) {
                    Edge& e = graph[u][i];
                    long long cost = e.cost + h[u] - h[e.to];
                    if (e.cap > 0 && dist[u] + cost < dist[e.to]) {
                        dist[e.to] = dist[u] + cost;
                        prevv[e.to] = u;
                        preve[e.to] = i;
                        pq.push({dist[e.to], e.to});
                    }
                }
            }
            if (dist[t] == LLONG_MAX) break;
            for (int i = 0; i < n; i++) {
                if (dist[i] != LLONG_MAX) {
                    h[i] += dist[i];
                }
            }
            long long d = maxFlow - flow;
            for (int v = t; v != s; v = prevv[v]) {
                d = min(d, graph[prevv[v]][preve[v]].cap);
            }
            for (int v = t; v != s; v = prevv[v]) {
                Edge& e = graph[prevv[v]][preve[v]];
                e.cap -= d;
                graph[v][e.rev].cap += d;
            }
            flow += d;
            cost += d * h[t];
        }
        return {flow, cost};
    }
};

Applications

• Assignment problem (minimum cost matching)
• $k$-edge shortest path
• Minimum weight matching in bipartite graphs

Example: Assignment Problem

long long minCostAssignment(int n, vector<vector<long long>>& cost) {
    MCMF mcmf(2 * n + 2);
    int s = 2 * n, t = 2 * n + 1;
    for (int i = 0; i < n; i++) {
        mcmf.addEdge(s, i, 1, 0);
    }
    for (int j = 0; j < n; j++) {
        mcmf.addEdge(n + j, t, 1, 0);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            mcmf.addEdge(i, n + j, 1, cost[i][j]);
        }
    }
    return mcmf.minCostMaxFlow(s, t).second;
}

Complexity

• SPFA-based: $O(F \cdot VE)$
• Dijkstra-based: $O(F \cdot E \log V)$

Tips

1. Use Hungarian for dense graphs, MCMF for sparse graphs or general flows.
2. For large costs, be careful with overflow.
3. For floating point costs, handle precision carefully.