Min Cost Flow

Wiki › Thuật toán › Luồng mạng (Network Flow)

huunguyen · Last updated 8, Tháng 4, 2026, 15:32

Min Cost Flow tìm luồng có tổng chi phí nhỏ nhất trong mạng có cả sức chứa lẫn chi phí trên cạnh. Bài toán: gửi $F$ đơn vị luồng từ $s$ đến $t$ với chi phí nhỏ nhất.

Cài đặt — SPFA (Bellman-Ford + augmenting path)

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

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

    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ề {max_flow, min_cost} khi gửi tối đa flow_limit đơn vị
    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 ngắn nhất (chi phí nhỏ nhất) trong residual graph
            vector<long long> dist(n, LLONG_MAX);
            vector<bool> in_queue(n, false);
            vector<int> prev_v(n, -1), prev_e(n, -1);

            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++) {
                    auto& e = graph[v][i];
                    if (e.cap > 0 && 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; }
                    }
                }
            }

            if (dist[t] == LLONG_MAX) break;

            // Tìm lượng luồng có thể gửi theo đường này
            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);

            // Cập nhật
            for (int v = t; v != s; v = prev_v[v]) {
                auto& e = graph[prev_v[v]][prev_e[v]];
                e.cap -= push;
                graph[v][e.rev].cap += push;
            }

            flow += push;
            cost += push * dist[t];
        }

        return {flow, cost};
    }
};

Ví dụ sử dụng

int main() {
    int n, m; cin >> n >> m;
    MinCostFlow mcf(n+1);   // 1-indexed

    for (int i = 0; i < m; i++) {
        int u, v, cap, cost; cin >> u >> v >> cap >> cost;
        mcf.add_edge(u, v, cap, cost);
    }

    auto [flow, cost] = mcf.min_cost_flow(1, n);
    cout << flow << " " << cost << "\n";
}

Ứng dụng

Bài toán phân công (Assignment Problem): $n$ công việc, $n$ nhân viên, chi phí $c_{i j}$ — đưa về min cost bipartite matching.
Vận chuyển hàng hóa: Gửi hàng qua mạng lưới phân phối với chi phí nhỏ nhất.
Successive Shortest Path: Mỗi lần augment đi qua đường ngắn nhất (chi phí nhỏ nhất).

Độ phức tạp

$O (F \cdot (V + E))$ với SPFA (F là tổng luồng), hoặc $O (V E \log V)$ với Dijkstra + potentials (Johnson's algorithm).

Lưu ý: Nếu có chi phí âm, dùng SPFA. Nếu không có chi phí âm, dùng Dijkstra với potentials để nhanh hơn.

Bình luận

Không có bình luận tại thời điểm này.