Pada Chapter graph dasar (max-flow min-cut), kita sudah mempelajari algoritma Edmonds-Karp untuk maximum flow. Sekarang kita naik ke persoalan yang lebih kaya: minimum cost maximum flow — di mana setiap edge punya kapasitas dan biaya per unit flow. Tujuannya: kirim flow maksimum dari s ke t dengan total cost minimum. Aplikasi: bipartite matching dengan cost assignment, job scheduling, transportation problem, dan banyak lagi. Selain itu, kita juga membahas reduksi bipartite matching ke max flow — skenario klasik di mana max flow algorithm memberi solusi matching. Pada Chapter ini kita mengimplementasikan Min Cost Max Flow dengan SPFA (Bellman-Ford queue-based), dan menyentuh aplikasi matching.

Aturan: Minimum Cost Maximum Flow #

Diberikan graph berarah berbobot dengan:

  • Setiap edge (u, v) punya kapasitas cap(u, v) ≥ 0 dan biaya cost(u, v) per unit flow.
  • Sumber s, tujuan t.

Min cost max flow: kirim flow maksimum dari s ke t (memenuhi capacity constraint dan flow conservation), sehingga total cost Σ f(u, v) × cost(u, v) minimum.

Bila edge backward punya cost negatif (-cost(u, v)), algoritma harus handle negative edge. SPFA (Shortest Path Faster Algorithm) berbasis Bellman-Ford mendukung ini.

Mekanisme: Successive Shortest Path #

Algoritma successive shortest path:

  1. Inisialisasi flow = 0.
  2. Selama ada augmenting path dari s ke t: a. Cari shortest path dari s ke t pada residual graph (dengan edge cost sebagai weight). Edge backward punya cost -cost(u,v). b. Hitung bottleneck (min residual capacity sepanjang path). c. Augment flow sebesar bottleneck. Tambah ke total_flow, tambahkan bottleneck × path_cost ke total_cost.
  3. Berhenti saat tidak ada augmenting path. Return (total_flow, total_cost).

Untuk shortest path dengan edge cost negatif (dari residual edge backward), gunakan SPFA atau Bellman-Ford. Bila semua edge cost non-negatif, Dijkstra dengan potential (Johnson’s algorithm) lebih cepat.

Implementasi Min Cost Max Flow #

cpp 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

class MinCostMaxFlow {
public:
    MinCostMaxFlow(int n) : n(n), graph(n) {}

    void add_edge(int u, int v, int cap, int cost) {
        graph[u].push_back({v, cap, cost, (int)graph[v].size()});
        graph[v].push_back({u, 0, -cost, (int)graph[u].size() - 1});
    }

    pair<long long, long long> min_cost_max_flow(int s, int t) {
        long long total_flow = 0, total_cost = 0;
        while (true) {
            vector<long long> dist(n, LLONG_MAX);
            vector<int> prev_node(n, -1), prev_edge(n, -1);
            vector<bool> in_queue(n, false);
            dist[s] = 0;
            queue<int> q;
            q.push(s);
            in_queue[s] = true;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                in_queue[u] = false;
                for (int i = 0; i < (int)graph[u].size(); ++i) {
                    auto& e = graph[u][i];
                    if (e.cap > 0 && dist[u] + e.cost < dist[e.to]) {
                        dist[e.to] = dist[u] + e.cost;
                        prev_node[e.to] = u;
                        prev_edge[e.to] = i;
                        if (!in_queue[e.to]) {
                            q.push(e.to);
                            in_queue[e.to] = true;
                        }
                    }
                }
            }
            if (dist[t] == LLONG_MAX) break;
            long long flow = LLONG_MAX;
            for (int v = t; v != s; v = prev_node[v]) {
                auto& e = graph[prev_node[v]][prev_edge[v]];
                flow = min(flow, (long long)e.cap);
            }
            for (int v = t; v != s; v = prev_node[v]) {
                auto& e = graph[prev_node[v]][prev_edge[v]];
                e.cap -= flow;
                graph[v][e.rev].cap += flow;
            }
            total_flow += flow;
            total_cost += flow * dist[t];
        }
        return {total_flow, total_cost};
    }

private:
    struct Edge {
        int to;
        int cap;
        int cost;
        int rev;
    };
    int n;
    vector<vector<Edge>> graph;
};

int main() {
    int n = 4;
    MinCostMaxFlow mcf(n);
    mcf.add_edge(0, 1, 10, 2);
    mcf.add_edge(0, 2, 5, 5);
    mcf.add_edge(1, 3, 8, 1);
    mcf.add_edge(2, 3, 10, 3);
    mcf.add_edge(1, 2, 3, 1);

    auto [flow, cost] = mcf.min_cost_max_flow(0, 3);
    cout << "Max flow: " << flow << '\n';
    cout << "Min cost: " << cost << '\n';

    cout << "\nVerifikasi manual:\n";
    cout << "Path 1: S->A->T cap min(10,8)=8, cost 2+1=3 per unit, flow 8, cost 8*3=24\n";
    cout << "Path 2: S->A->B->T cap min(2,3,10)=2, cost 2+1+3=6 per unit, flow 2, cost 2*6=12 (total 36)\n";
    cout << "Path 3: S->B->T cap min(5,8)=5, cost 5+3=8 per unit, flow 5, cost 5*8=40 (total 76)\n";
    cout << "Max flow = 8+2+5 = 15 (habis, S outgoing cap 10+5=15)\n";
    cout << "Min cost = 76\n";
    return 0;
}

Output yang Dihasilkan:

text 
Max flow: 15
Min cost: 76

Verifikasi manual:
Path 1: S->A->T cap min(10,8)=8, cost 2+1=3 per unit, flow 8, cost 8*3=24
Path 2: S->A->B->T cap min(2,3,10)=2, cost 2+1+3=6 per unit, flow 2, cost 2*6=12 (total 36)
Path 3: S->B->T cap min(5,8)=5, cost 5+3=8 per unit, flow 5, cost 5*8=40 (total 76)
Max flow = 8+2+5 = 15 (habis, S outgoing cap 10+5=15)
Min cost = 76

Bedah Kode Baris-per-Baris #

  1. struct Edge { int to, cap, cost, rev; }: edge dengan tujuan, kapasitas residual, cost per unit, dan indeks edge backward (untuk fast access saat augment).
  2. add_edge(u, v, cap, cost): tambahkan edge forward u → v dengan capacity cap, cost cost. Tambahkan edge backward v → u dengan capacity 0 (initially no reverse flow), cost -cost (membatalkan flow forward = mengembalikan biaya).
  3. graph[v].size() sebagai rev: indeks edge backward = posisi edge baru di graph[v]. Dipakai saat augment untuk update kedua edge.
  4. SPFA loop: queue-based Bellman-Ford. Setiap node di-push ke queue bila dist-nya di-relax. in_queue flag mencegah duplikat entry. Kompleksitas worst case O(VE) tetapi biasanya jauh lebih cepat.
  5. if (e.cap > 0 && dist[u] + e.cost < dist[e.to]): hanya ikuti edge dengan kapasitas residual > 0, dan relax bila menemukan path lebih pendek.
  6. if (dist[t] == LLONG_MAX) break: bila t tidak terjangkau, tidak ada augmenting path → selesai.
  7. Bottleneck: iterasi dari t ke s via prev_node, cari kapasitas residual minimum.
  8. Augment: untuk setiap edge di path, kurangi cap forward, tambah cap backward (di graph[v][e.rev]).
  9. total_cost += flow * dist[t]: setiap unit flow di path menambah cost sebesar path_cost = dist[t]. Total cost = Σ flow_i × path_cost_i.
  10. Verifikasi:
    • Path 1: S→A→T. Bottleneck min(10, 8) = 8. Cost = 2 + 1 = 3 per unit. Augment 8 → total flow 8, total cost 24.
    • Path 2: S→A→B→T. Setelah path 1, S→A sisa 2, A→B penuh (3), B→T penuh (10). Bottleneck min(2, 3, 10) = 2. Cost = 2 + 1 + 3 = 6 per unit. Augment 2 → total flow 10, total cost 24 + 12 = 36.
    • Path 3: S→B→T. S→B cap 5, B→T sisa 8. Bottleneck min(5, 8) = 5. Cost = 5 + 3 = 8 per unit. Augment 5 → total flow 15, total cost 36 + 40 = 76.
    • Setelah path 3: S→A cap 0, S→B cap 0. S tidak bisa kirim lebih → max flow = 15. Min cost = 76. ✓

Reduksi Bipartite Matching ke Max Flow #

Bipartite matching: graph bipartit (L, R, E). Cari matching maksimum (set node berpasangan tanpa konflik).

Reduksi ke max flow:

  1. Tambah source s dengan edge ke semua node di L (capacity 1).
  2. Tambah sink t dengan edge dari semua node di R (capacity 1).
  3. Edge original L → R tetap dengan capacity 1.
  4. Max flow s → t = max bipartite matching.

Untuk weighted bipartite matching (minimum cost perfect matching), gunakan min cost max flow. Hungarian algorithm adalah alternatif khusus untuk masalah ini dengan kompleksitas O(n³).

Kompleksitas #

AlgoritmaKompleksitasKeterangan
Edmonds-Karp (max flow)O(V · E²)BFS-based
Dinic (max flow)O(V² · E)Lebih cepat untuk dense
Min cost max flow (SPFA)O(F · V · E)F = max flow value
Min cost max flow (Dijkstra + potential)O(F · E log V)Lebih cepat, all non-neg
Hungarian (bipartite perfect matching)O(n³)Khusus bipartite lengkap

Aplikasi #

  1. Bipartite matching (unweighted dan weighted): reduksi ke max flow / min cost max flow.
  2. Job assignment: n pekerja, n pekerjaan, setiap pasangan punya cost. Cari assignment min cost → bipartite matching.
  3. Transportation problem: m supply nodes, n demand nodes, cost per unit. Cari distribusi min cost.
  4. Circulation problem: flow conservation untuk semua node (tidak ada s/t). Tambah edge t → s dengan capacity ∞ → reduksi ke max flow.
  5. Project selection: pilih subset proyek dengan dependency constraint. Reduksi ke min cut.

Ringkasan #

  • Min cost max flow = kirim flow maksimum dengan total cost minimum.
  • Successive shortest path: ulang cari shortest augmenting path (dengan cost) dan augment.
  • SPFA (Bellman-Ford queue-based) menangani edge cost negatif (dari residual edge backward).
  • Edge backward dengan cost -cost(u, v) memungkinkan “membatalkan” flow dan mendapat kembali biaya.
  • Reduksi bipartite matching ke max flow: tambah source ke semua left, semua right ke sink.
  • Kompleksitas O(F · V · E) untuk SPFA-based. Dengan potential (Johnson) bisa O(F · E log V).
  • Aplikasi: bipartite matching, job assignment, transportation, circulation, project selection.