Min Cost Max Flow

Minimum Cost Maximum Flow Algorithm

Min Cost Max Flow (MCMF)

Minimum Cost Maximum Flow หา flow ที่มี value สูงสุด และมี cost รวมต่ำสุด

Problem Definition

แต่ละ edge มี capacity $c(u,v)$ และ cost $w(u,v)$
Cost ของ flow $f$ คือ $\sum f(u,v) \cdot w(u,v)$
หา max flow ที่มี min cost

SPFA-based MCMF

ใช้ SPFA (Shortest Path Faster Algorithm) หา shortest path ใน 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});
    }
    
    // SPFA to find shortest path
    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)) {
            // Find bottleneck
            long long d = maxFlow - flow;
            for (int v = t; v != s; v = prevv[v]) {
                d = min(d, graph[prevv[v]][preve[v]].cap);
            }
            
            // Augment flow
            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)

ใช้ Dijkstra แทน SPFA โดยใช้ Johnson’s potentials เพื่อจัดการ negative edges

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) {
            // Dijkstra
            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;
            
            // Update potentials
            for (int i = 0; i < n; i++) {
                if (dist[i] != LLONG_MAX) {
                    h[i] += dist[i];
                }
            }
            
            // Find bottleneck
            long long d = maxFlow - flow;
            for (int v = t; v != s; v = prevv[v]) {
                d = min(d, graph[prevv[v]][preve[v]].cap);
            }
            
            // Augment
            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};
    }
};

ประยุกต์ใช้งาน

1. Assignment Problem

หา assignment ที่มี cost น้อยที่สุด

long long minCostAssignment(int n, vector<vector<long long>>& cost) {
    MCMF mcmf(2 * n + 2);
    int s = 2 * n, t = 2 * n + 1;
    
    // Source to workers
    for (int i = 0; i < n; i++) {
        mcmf.addEdge(s, i, 1, 0);
    }
    
    // Jobs to sink
    for (int j = 0; j < n; j++) {
        mcmf.addEdge(n + j, t, 1, 0);
    }
    
    // Workers to jobs
    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;
}

2. K-Edge Shortest Path

หา shortest path ที่ผ่าน exactly k edges

long long kEdgeShortestPath(int n, int m, int s, int t, int k, 
                            vector<tuple<int, int, long long>>& edges) {
    // Split each node (except s, t) into k+1 copies
    // Or use MCMF with flow = k
    
    MCMF mcmf(n);
    for (auto& [u, v, w] : edges) {
        mcmf.addEdge(u, v, 1, w);
    }
    
    auto [flow, cost] = mcmf.minCostMaxFlow(s, t, k);
    
    if (flow < k) return -1;  // No valid path
    return cost;
}

3. Minimum Weight Matching

หา matching ใน bipartite graph ที่มี total weight น้อยที่สุด

long long minWeightMatching(int n, int m, vector<tuple<int, int, long long>>& edges) {
    MCMF mcmf(n + m + 2);
    int s = n + m, t = n + m + 1;
    
    for (int i = 0; i < n; i++) {
        mcmf.addEdge(s, i, 1, 0);
    }
    
    for (int j = 0; j < m; j++) {
        mcmf.addEdge(n + j, t, 1, 0);
    }
    
    for (auto& [u, v, w] : edges) {
        mcmf.addEdge(u, n + v, 1, w);
    }
    
    return mcmf.minCostMaxFlow(s, t).second;
}

Complexity

Algorithm	Time Complexity
SPFA-based	$O(VE \cdot flow)$
Dijkstra-based	$O(flow \cdot E \log V)$
Bellman-Ford based	$O(VE \cdot flow)$

Tips

Negative costs - SPFA version handles negative costs automatically
Potentials - Dijkstra version is faster but requires potential adjustment
Integer overflow - ระวัง cost อาจ overflow เมื่อ sum up
Flow limit - บางครั้งต้องหา min cost สำหรับ specific flow value