Min Cost Flow

Min Cost Flow (luồng cực đại chi phí nhỏ nhất, viết tắt MCMF — Min Cost Max Flow) giải bài toán: trong một mạng mà mỗi cạnh vừa có sức chứa (capacity) vừa có chi phí trên một đơn vị luồng (cost), hãy đẩy một lượng luồng cho trước (hoặc luồng cực đại) từ nguồn $s$ tới đích $t$ sao cho tổng chi phí nhỏ nhất.

Đây là tổng quát hoá của bài toán luồng cực đại: ngoài việc tối đa hoá lượng luồng, ta còn muốn trả ít tiền nhất. Rất nhiều bài toán tối ưu hoá tổ hợp (phân công, vận tải, ghép đôi có trọng số) quy về MCMF. Thuật toán chuẩn (SSP — Successive Shortest Paths) chạy trong $O(F·(V+E)\log V)$ hoặc $O(F·VE)$ tuỳ cách tìm đường, trong đó $F$ là tổng lượng luồng cần đẩy — nhanh hơn nhiều so với việc liệt kê mọi cách phân bổ.

Ý tưởng / Trực giác

Ý tưởng cốt lõi: lặp đi lặp lại việc đẩy luồng dọc theo đường tăng luồng (augmenting path) RẺ NHẤT, thay vì đường bất kỳ như trong Ford–Fulkerson thông thường.

Vì sao điều này cho ra tổng chi phí nhỏ nhất? Dựa trên một định lý kinh điển:

Nếu luồng hiện tại $f$ đang là luồng rẻ nhất trong số mọi luồng có cùng giá trị $|f|$, thì sau khi tăng thêm dọc theo đường ngắn nhất (theo chi phí) trong đồ thị thặng dư (residual graph), luồng mới cũng rẻ nhất trong số mọi luồng có giá trị $|f|+\Delta$.

Nói cách khác, ta xây dựng lời giải tối ưu từng lớp: luồng giá trị 0 rẻ nhất (chi phí 0); rồi mỗi lần tăng luồng theo đường rẻ nhất, ta giữ được tính tối ưu cho giá trị luồng mới. Đây chính là một dạng quy hoạch lồi (đường cong chi phí theo lượng luồng là lồi — đẩy mỗi đơn vị luồng tiếp theo không bao giờ rẻ hơn đơn vị trước).

Điểm mấu chốt là cạnh ngược (residual edge). Khi đẩy luồng qua cạnh $u\to v$ với chi phí $w$, ta tạo cạnh ngược $v\to u$ với chi phí $-w$. Cạnh âm này cho phép thuật toán "hoàn tác" một quyết định cũ nếu sau này phát hiện cách rẻ hơn — đây là lý do ta cần thuật toán tìm đường ngắn nhất xử lý được trọng số âm (Bellman–Ford / SPFA), chứ không dùng Dijkstra thuần.

Vì sao đường rẻ nhất không tạo chu trình âm? Do bất biến ở trên: nếu luồng hiện tại đã tối ưu cho giá trị của nó, thì đồ thị thặng dư không chứa chu trình chi phí âm — nếu có thì ta đã có thể giảm chi phí mà không đổi giá trị luồng, mâu thuẫn với "đang tối ưu". Nhờ vậy thuật toán tìm đường ngắn nhất luôn hợp lệ ở mỗi bước.

Ví dụ chạy tay

Mạng có 4 đỉnh: nguồn $s=0$, $t=3$. Mỗi cạnh ghi (cap, cost). Ta cần đẩy 2 đơn vị luồng từ $s$ tới $t$.

        (1, 1)
    0 -----------> 1
    |              |
(2,2)|              |(2,1)
    |              |
    v              v
    2 -----------> 3
        (2, 3)
   và cạnh 1 -> 2 (1, 1)

Liệt kê cạnh:

• $0\to 1$ : cap 1, cost 1
• $0\to 2$ : cap 2, cost 2
• $1\to 3$ : cap 2, cost 1
• $1\to 2$ : cap 1, cost 1
• $2\to 3$ : cap 2, cost 3

Vòng 1 — tìm đường rẻ nhất từ 0 đến 3. Chạy SPFA, mảng dist:

Đường rẻ nhất: $0\to 1\to 3$, chi phí $1+1=2$. Nút cổ chai (bottleneck) = $min({\text{cap}}_{0\to 1},{\text{cap}}_{1\to 3})=min(1,2)=1$.

Đẩy 1 đơn vị. Cập nhật cap (giảm chiều thuận, tăng chiều ngược):

0 ->1 : cap 1->0   (ngược 1->0 : cap 0->1)
1 ->3 : cap 2->1   (ngược 3->1 : cap 0->1)

Trạng thái: flow = 1, cost = 1 * 2 = 2.

Vòng 2 — tìm lại đường rẻ nhất. Cạnh $0\to 1$ đã hết chỗ (cap 0). SPFA mới:

Đường rẻ nhất còn lại: $0\to 2\to 3$, chi phí $2+3=5$. Bottleneck $=min(2,2)=2$, nhưng ta chỉ còn cần $2-1=1$ đơn vị nữa, nên push = min(2, 1) = 1.

Đẩy 1 đơn vị. Trạng thái: flow = 2, cost = 2 + 1*5 = 7.

Đã đủ 2 đơn vị → dừng. Kết quả: luồng = 2, tổng chi phí = 7.

Lưu ý: đáp án này tối ưu vì ở mỗi vòng ta luôn chọn đường rẻ nhất hiện có ($2$ rồi $5$); không có cách đẩy 2 đơn vị nào rẻ hơn $2+5=7$.

Cài đặt

Cài đặt bằng SPFA (Bellman–Ford dạng hàng đợi) để xử lý được cạnh ngược chi phí âm. Mỗi vòng tìm một đường rẻ nhất rồi đẩy tối đa dọc đường đó.

#include <bits/stdc++.h>
using namespace std;

struct MinCostFlow {
    struct Edge { int to, rev; long long cap, cost; };
    vector<vector<Edge>> graph;
    int n;

    MinCostFlow(int n) : n(n), graph(n) {}

    // Thêm cạnh có hướng from->to: sức chứa cap, chi phí cost mỗi đơn vị.
    // Đồng thời thêm cạnh ngược to->from: cap 0, cost -cost (để hoàn tác).
    void add_edge(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});
    }

    // Trả về {tổng luồng đẩy được, tổng chi phí}.
    // flow_limit: chặn trên lượng luồng (mặc định = vô hạn => luồng cực đại).
    pair<long long, long long> min_cost_flow(int s, int t,
                                             long long flow_limit = LLONG_MAX) {
        long long flow = 0, cost = 0;

        while (flow < flow_limit) {
            // SPFA tìm đường rẻ nhất s -> t trong đồ thị thặng dư.
            vector<long long> dist(n, LLONG_MAX);
            vector<bool> in_queue(n, false);
            vector<int> prev_v(n, -1), prev_e(n, -1); // truy vết đường đi

            dist[s] = 0;
            queue<int> q;
            q.push(s); in_queue[s] = true;

            while (!q.empty()) {
                int v = q.front(); q.pop();
                in_queue[v] = false;
                for (int i = 0; i < (int)graph[v].size(); i++) {
                    Edge& e = graph[v][i];
                    // chỉ đi qua cạnh còn chỗ và làm giảm khoảng cách
                    if (e.cap > 0 && dist[v] != LLONG_MAX
                        && dist[v] + e.cost < dist[e.to]) {
                        dist[e.to] = dist[v] + e.cost;
                        prev_v[e.to] = v;
                        prev_e[e.to] = i;
                        if (!in_queue[e.to]) {
                            q.push(e.to);
                            in_queue[e.to] = true;
                        }
                    }
                }
            }

            // Không còn đường tăng luồng tới t => dừng.
            if (dist[t] == LLONG_MAX) break;

            // Tìm nút cổ chai dọc đường vừa tìm được.
            long long push = flow_limit - flow;
            for (int v = t; v != s; v = prev_v[v])
                push = min(push, graph[prev_v[v]][prev_e[v]].cap);

            // Đẩy luồng: giảm chiều thuận, tăng chiều ngược.
            for (int v = t; v != s; v = prev_v[v]) {
                Edge& e = graph[prev_v[v]][prev_e[v]];
                e.cap -= push;
                graph[v][e.rev].cap += push; // cạnh ngược tăng theo
            }

            flow += push;
            cost += push * dist[t]; // chi phí = lượng đẩy * giá đường này
        }

        return {flow, cost};
    }
};

Ví dụ dùng cho bài toán phân công ($n$ công nhân, $n$ việc): tạo nguồn $S$ nối tới mỗi công nhân (cap 1, cost 0), mỗi công nhân $i$ nối tới việc $j$ (cap 1, cost $c_{ij}$), mỗi việc nối tới đích $T$ (cap 1, cost 0). Gọi min_cost_flow(S, T) cho ra tổng chi phí phân công nhỏ nhất.

Độ phức tạp

Gọi $V$ = số đỉnh, $E$ = số cạnh, $F$ = tổng lượng luồng cần đẩy.

• Thời gian: $O(F·VE)$ với SPFA như trên. Mỗi vòng while đẩy ít nhất 1 đơn vị luồng (thường nhiều hơn nhờ bottleneck), nên số vòng $\le F$. Mỗi vòng chạy một lần SPFA, trường hợp xấu nhất $O(VE)$. Nếu các sức chứa là số nguyên nhỏ và đồ thị thưa thì thực tế chạy rất nhanh.
• Nếu thay SPFA bằng Dijkstra + thế năng Johnson (Johnson potentials) để khử trọng số âm, mỗi vòng giảm còn $O(E\log V)$, tổng $O(F·E\log V)$ — đáng dùng khi $F$ nhỏ nhưng đồ thị lớn.
• Bộ nhớ: $O(V+E)$ cho danh sách kề (mỗi cạnh lưu kèm một cạnh ngược, tức $2E$ phần tử), cộng $O(V)$ cho các mảng dist, prev_v, prev_e, in_queue mỗi lần SPFA.

Vì sao $F$ xuất hiện trong độ phức tạp? Vì mỗi vòng chỉ tăng giá trị luồng một lượng, nên muốn đạt luồng $F$ cần tới $F$ vòng (xấu nhất). Đây là lý do MCMF chỉ thực tế khi $F$ không quá lớn (bài toán thường chọn dữ liệu để $F$ nhỏ, ví dụ $F\le 100$ hoặc $F=n$).

⚠️ Lỗi thường gặp

• Tràn số (overflow): tổng chi phí = (lượng luồng) × (chi phí đường) cộng dồn nhiều vòng, dễ vượt int. Luôn để cap và cost kiểu long long. Một test với $F={10}^4$ và chi phí cạnh ${10}^4$ đã cho tổng $~{10}^8$–${10}^9$, biên int rất nguy hiểm.
• Dùng Dijkstra thuần trên cạnh âm: đồ thị thặng dư có cạnh ngược chi phí âm. Dijkstra thuần sẽ cho khoảng cách SAI. Phải dùng SPFA/Bellman–Ford, hoặc Dijkstra kèm thế năng (Johnson). Triệu chứng: đáp án nhỏ hơn/khác đáp án đúng ở các test có đường hoàn tác.
• Khởi tạo dist chưa kiểm tra vô hạn: điều kiện nới lỏng phải có dist[v] != LLONG_MAX trước khi tính dist[v] + e.cost. Quên kiểm tra sẽ làm LLONG_MAX + cost tràn xuống số âm và "mở khoá" những cạnh không nên đi — đáp án sai một cách khó hiểu.
• Quên cạnh ngược hoặc đặt sai chi phí cạnh ngược: cạnh ngược phải có cap = 0 và cost = -cost. Nếu để chi phí cạnh ngược bằng +cost, thuật toán không hoàn tác được và cho luồng tối ưu cục bộ sai. Nếu để cap cạnh ngược khác 0, sẽ tạo luồng "ma".
• Lẫn lộn rev (chỉ số cạnh ngược): khi add_edge, rev của cạnh thuận phải là kích thước hiện tại của graph[to] (vị trí cạnh ngược sắp thêm), và rev của cạnh ngược là graph[from].size() - 1. Sai chỉ số này làm việc cập nhật cạnh ngược ghi nhầm cạnh khác.
• Vòng lặp vô tận khi mạng có chu trình chi phí âm sẵn trong đầu vào: thuật toán SSP giả định không có chu trình âm ban đầu. Nếu bài cho phép cạnh chi phí âm tạo chu trình âm, cần khử trước (vd kỹ thuật negative cycle canceling), nếu không SPFA có thể không hội tụ.
• Đặt flow_limit sai cho bài "đẩy đúng $k$ đơn vị": với bài như vận chuyển đúng $k$ kiện hàng, phải truyền flow_limit = k và kiểm tra flow == k ở cuối; nếu flow < k nghĩa là không đủ sức chứa, phải in $-1$ thay vì in chi phí của luồng chưa đủ.

Biến thể / Mở rộng

• Min cost max flow: gọi min_cost_flow(s, t) không giới hạn → vừa cực đại hoá luồng vừa cực tiểu hoá chi phí.
• Đẩy đúng $k$ đơn vị: truyền flow_limit = k.
• Tối đa hoá lợi nhuận: nếu cạnh có "lãi" thay vì "chi phí", nhân chi phí với $-1$ rồi tìm min cost (hoặc dừng sớm khi đường rẻ nhất bắt đầu mang chi phí dương).
• Dijkstra + thế năng (Johnson potentials): tăng tốc cho đồ thị lớn, $F$ nhỏ; biến mọi cạnh thành chi phí không âm nhờ thế năng $h[v]$ cập nhật sau mỗi vòng.
• Liên hệ: MCMF là tổng quát của luồng cực đại (bỏ chi phí) và là công cụ giải bài toán phân công (assignment) cũng như ghép đôi có trọng số (weighted bipartite matching).

Bài tập luyện

• Bài Toán Phân Công (assgn) — (Kỳ cựu) Bài phân công kinh điển $n$ công nhân–$n$ việc: dựng mạng $S\to$ công nhân $\to$ việc $\to T$, mỗi cạnh công nhân–việc cost $c_{ij}$, chạy MCMF lấy tổng chi phí nhỏ nhất và truy vết cách ghép.
• Giao Hàng (parceldeliv) — (Kỳ cựu) MCMF trực tiếp nhất: mỗi tuyến đường là cạnh có sức chứa $r$ và chi phí $c$/đơn vị; đặt flow_limit = k, kiểm tra đẩy đủ $k$ kiện hay in $-1$.
• Ghép Đôi Platinum (pairedup21) — (Chuyên gia) Ghép đôi có ràng buộc khoảng cách và trọng số, cần mô hình hoá khéo thành luồng chi phí nhỏ nhất/lớn nhất — luyện kỹ năng dựng mạng cho bài tối ưu tổ hợp.