Minimum Cost Flow

ITăng luồng theo đường đi rẻ nhất

Một mạng có chi phí gồm các cung $u \to v$, mỗi cung có sức chứa $c(u, v)$ và chi phí $a(u, v)$ cho mỗi đơn vị luồng; luồng $f(u, v)$ trên cung đó tốn $f(u, v) \cdot a(u, v)$, và chi phí của luồng là tổng trên mọi cung. Ta muốn một luồng giá trị đúng $k$ có chi phí nhỏ nhất. Nếu mạng không có luồng giá trị $k$ thì không có đáp án.

Cách vét cạn là thử mọi cách phân $k$ đơn vị lên các cung, quá nhiều khi đồ thị lớn. Ta có thể bắt đầu từ cách của bài luồng cực đại: lần lượt tăng luồng theo các đường tăng luồng (bài 4.9.1). Câu hỏi là chọn đường nào. Nếu chọn đường tùy ý thì luồng có thể đắt hơn mức cần thiết; nếu mỗi lần chọn đường rẻ nhất trong đồ thị dư thì kết quả tối ưu. Cung ngược $v \to u$ của cung $u \to v$ có chi phí $-a(u, v)$, vì rút lại một đơn vị hàng cũng lấy lại tiền đã tốn.

Ví dụ nhỏ: mạng có bốn đỉnh $s, a, b, t$ và năm cung, mọi sức chứa đều là 1. Các cung $s \to a$, $a \to b$ và $b \to t$ có chi phí 1; cung $s \to b$ và $a \to t$ có chi phí 4. Ta cần $k = 2$ đơn vị. Đường rẻ nhất là $s \to a \to b \to t$, chi phí 3. Sau khi đẩy một đơn vị theo đó, ba cung của đường này đầy, đồ thị dư chỉ còn ba cung như hình, và đường tăng luồng duy nhất là $s \to b \to a \to t$ với chi phí $4 + (-1) + 4 = 7$. Tổng chi phí là $3 + 7 = 10$, đúng bằng cách đi riêng $s \to a \to t$ và $s \to b \to t$, tốn $5 + 5$.

Vì có cung chi phí âm nên không dùng Dijkstra thẳng được. Ta dùng SPFA, tức thuật toán Bellman-Ford có hàng đợi: một đỉnh được đưa vào hàng đợi mỗi khi khoảng cách tới nó giảm, và khi lấy ra, ta thử cải thiện khoảng cách tới các đỉnh kề. SPFA đúng với chi phí âm miễn là đồ thị không có chu trình âm; đồ thị dư của ta không có (xem ô Chứng minh).

Mỗi lần đẩy ta lấy lượng bằng sức chứa nhỏ nhất trên đường, nhưng không vượt quá số đơn vị còn thiếu. Chi phí tăng thêm bằng lượng đẩy nhân chi phí của đường.

Ví dụChuyển Kiện Tiết Kiệm

Đề. Có $n \le 500$ thành phố và $m \le 1000$ tuyến vận chuyển có hướng; tuyến $a \to b$ chở tối đa $r$ kiện và mỗi kiện qua tuyến đó tốn $c$ ($1 \le r, c \le 1000$). Cần chuyển đúng $k \le 100$ kiện từ thành phố $1$ tới thành phố $n$. In tổng chi phí nhỏ nhất, hoặc $-1$ nếu không đủ sức chứa.

Lời giải. Mỗi tuyến là một cung với sức chứa $r$ và chi phí $c$, và ta cần luồng giá trị $k$ nhỏ nhất chi phí. Ta tăng luồng cho tới khi đủ $k$ đơn vị hoặc không còn đường; nếu chưa đủ thì in $-1$. Mảng pe[v] ghi cung dẫn vào $v$ trên đường rẻ nhất, từ đó đi ngược từ $t$ về $s$.

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

const ll N = 505, M = 2005, INF = 1e18;
ll n, m, k, ec, to[M], cap[M], cost[M], d[N], pe[N], inq[N];
vector<ll> g[N];

void addEdge(ll u, ll v, ll c, ll w) {
    to[ec] = v, cap[ec] = c, cost[ec] = w, g[u].push_back(ec++);
    to[ec] = u, cap[ec] = 0, cost[ec] = -w, g[v].push_back(ec++);
}

bool spfa(ll s, ll t) {
    for (ll i = 1; i <= n; i++) d[i] = INF, inq[i] = 0;
    queue<ll> q;
    d[s] = 0;
    q.push(s);
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        inq[u] = 0;
        for (ll e : g[u])
            if (cap[e] > 0 && d[u] + cost[e] < d[to[e]]) {
                d[to[e]] = d[u] + cost[e];
                pe[to[e]] = e;
                if (!inq[to[e]]) inq[to[e]] = 1, q.push(to[e]);
            }
    }
    return d[t] < INF;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> k;
    for (ll i = 1; i <= m; i++) {
        ll a, b, r, c;
        cin >> a >> b >> r >> c;
        addEdge(a, b, r, c);
    }
    ll flow = 0, ans = 0;
    while (flow < k && spfa(1, n)) {
        ll f = k - flow;
        for (ll v = n; v != 1; v = to[pe[v] ^ 1]) f = min(f, cap[pe[v]]);
        for (ll v = n; v != 1; v = to[pe[v] ^ 1]) {
            cap[pe[v]] -= f;
            cap[pe[v] ^ 1] += f;
        }
        flow += f;
        ans += f * d[n];
    }
    cout << (flow < k ? -1 : ans) << '\n';
}

ChạyInput4 5 3
1 2 5 100
1 3 10 50
1 4 7 500
2 4 8 350
3 4 2 100

Output750

Độ phức tạp: mỗi lần tăng luồng đẩy ít nhất 1 đơn vị nên có không quá $k$ lần, mỗi lần SPFA tốn $O(VE)$ trong trường hợp xấu nhất; với $k = 100$, $V = 500$, $E = 2000$ (tính cả cung ngược) cận này là $10^8$, và thực tế SPFA nhanh hơn nhiều.

IIThế đỉnh và Dijkstra

SPFA có thể chậm khi đồ thị lớn. Ta muốn dùng Dijkstra, nhưng nó cần mọi cung không âm. Thế đỉnh (potential) là một số $h(v)$ gán cho mỗi đỉnh, dùng để đổi chi phí của cung $u \to v$ thành chi phí rút gọn

Mọi đường đi từ $s$ tới $t$ có chi phí rút gọn bằng chi phí thật cộng $h(s) - h(t)$, vì các $h$ ở giữa triệt tiêu, nên đường nào ngắn nhất theo chi phí rút gọn cũng ngắn nhất theo chi phí thật. Nếu chọn $h$ làm cho mọi cung của đồ thị dư có $a' \ge 0$ thì Dijkstra dùng được.

Cách chọn $h$ là dùng chính khoảng cách đã tính. Sau mỗi lần Dijkstra, ta có khoảng cách rút gọn $d'(v)$ từ $s$, và cập nhật $h(v) \gets h(v) + d'(v)$. Khi đó chi phí thật của đường ngắn nhất tới $t$ chính là $h(t)$, vì $h(s) = 0$ luôn đúng. Các cung nằm trên đường vừa đẩy có chi phí rút gọn mới bằng $0$, nên cung ngược của chúng cũng $0$, và các cung khác vẫn không âm theo ý của ô Chứng minh ở mục trên. Đỉnh không tới được thì giữ nguyên thế: về sau nó vẫn không tới được.

Còn thế ban đầu: nếu mọi cung của mạng có chi phí không âm thì chọn $h = 0$. Nếu có cung chi phí âm, ta chạy Bellman-Ford một lần từ $s$ để có $h$ ban đầu, sau đó chỉ dùng Dijkstra.

Ví dụPhân Công Tối Ưu

Đề. Có $n \le 200$ nhân viên và $n$ công việc; nhân viên $i$ nhận công việc $j$ tốn $c_i[j]$ ($1 \le c_i[j] \le 1000$). Mỗi nhân viên nhận đúng một công việc và mỗi công việc giao cho đúng một nhân viên. In tổng chi phí nhỏ nhất và một phép gán tối ưu (mỗi dòng gồm nhân viên và công việc được giao).

Lời giải. Dựng mạng $S \to$ nhân viên $\to$ công việc $\to T$. Mỗi cung $S \to i$ và mỗi cung công việc $\to T$ có sức chứa 1 và chi phí 0; cung nhân viên $i \to$ công việc $j$ có sức chứa 1 và chi phí $c_i[j]$. Một luồng giá trị $n$ phải đẩy đủ $n$ đơn vị qua $n$ cung ra khỏi $S$, mỗi nhân viên đúng một đơn vị, mỗi công việc đúng một đơn vị, nên nó chính là một phép gán, và chi phí của luồng là tổng chi phí phép gán. Luồng chi phí nhỏ nhất cho phép gán tối ưu. Các cung nhân viên $\to$ công việc đã đầy (sức chứa dư bằng 0) cho biết ai nhận việc nào. Mạng có $2n + 2$ đỉnh và $n^2 + 2n$ cung, nên Dijkstra với thế đỉnh thích hợp; Hungary (thuật toán chuyên cho bài phân công, $O(n^3)$) là một lựa chọn khác.

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

const ll N = 405, M = 81005, INF = 1e18;
ll n, V, ec, to[M], cap[M], cost[M], h[N], d[N], pe[N];
vector<ll> g[N];

void addEdge(ll u, ll v, ll c, ll w) {
    to[ec] = v, cap[ec] = c, cost[ec] = w, g[u].push_back(ec++);
    to[ec] = u, cap[ec] = 0, cost[ec] = -w, g[v].push_back(ec++);
}

bool dijkstra(ll s, ll t) {
    for (ll i = 0; i < V; i++) d[i] = INF;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > q;
    d[s] = 0;
    q.push(make_pair(0, s));
    while (!q.empty()) {
        ll du = q.top().first, u = q.top().second;
        q.pop();
        if (du > d[u]) continue;
        for (ll e : g[u]) {
            ll v = to[e], nd = du + cost[e] + h[u] - h[v];
            if (cap[e] > 0 && nd < d[v]) {
                d[v] = nd;
                pe[v] = e;
                q.push(make_pair(nd, v));
            }
        }
    }
    if (d[t] >= INF) return 0;
    for (ll i = 0; i < V; i++)
        if (d[i] < INF) h[i] += d[i];
    return 1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    ll s = 0, t = 2 * n + 1;
    V = 2 * n + 2;
    for (ll i = 1; i <= n; i++) {
        addEdge(s, i, 1, 0);
        addEdge(n + i, t, 1, 0);
        for (ll j = 1; j <= n; j++) {
            ll c;
            cin >> c;
            addEdge(i, n + j, 1, c);
        }
    }
    ll ans = 0;
    while (dijkstra(s, t)) {
        ll f = INF;
        for (ll v = t; v != s; v = to[pe[v] ^ 1]) f = min(f, cap[pe[v]]);
        for (ll v = t; v != s; v = to[pe[v] ^ 1]) {
            cap[pe[v]] -= f;
            cap[pe[v] ^ 1] += f;
        }
        ans += f * h[t];
    }
    cout << ans << '\n';
    for (ll i = 1; i <= n; i++)
        for (ll e : g[i])
            if (e % 2 == 0 && to[e] > n && to[e] <= 2 * n && cap[e] == 0) cout << i << ' ' << to[e] - n << '\n';
}

ChạyInput4
17 8 16 9
7 15 12 19
6 9 10 11
14 7 13 10

Output33
1 4
2 1
3 3
4 2

Độ phức tạp: có $n$ lần tăng luồng, mỗi lần Dijkstra tốn $O(E \log V)$ với $E \approx n^2$; với $n = 200$ cần khoảng $200 \cdot 4 \cdot 10^4 \cdot 9 \approx 7 \cdot 10^7$ phép tính.

IIICác bài quy về luồng chi phí nhỏ nhất

Nhiều bài trông không liên quan cũng đưa được về luồng chi phí nhỏ nhất: phân công, vận chuyển từ nhiều nguồn tới nhiều đích (thêm một nguồn chung nối tới các nguồn thật), và chọn đối tượng với giới hạn số lần dùng (sức chứa của cung là giới hạn đó). Điều cần làm là xác định ba thứ: đỉnh là gì, cung nào có sức chứa bao nhiêu, và đại lượng cần tối thiểu là chi phí của cung nào.

Ví dụĐội Giao Hàng Không Chung Cung

Đề. Có $n \le 500$ điểm và $m \le 1000$ tuyến một chiều. Phải chọn đúng $k$ lộ trình từ điểm $1$ tới điểm $n$ sao cho mỗi tuyến được dùng trong nhiều nhất một lộ trình, và tổng số tuyến đã đi là nhỏ nhất. In $-1$ nếu không chọn được; nếu được, in tổng số tuyến, rồi với mỗi lộ trình in số đỉnh trên đường và dãy đỉnh.

Lời giải. Gán cho mỗi tuyến sức chứa 1 (mỗi tuyến dùng tối đa một lần) và chi phí 1 (mỗi tuyến đã đi đếm là một). Khi đó $k$ lộ trình không chung cung cho một luồng nguyên giá trị $k$, và chi phí luồng chính là tổng số tuyến. Ngược lại, từ một luồng nguyên giá trị $k$ ta lấy lại được $k$ lộ trình không chung cung bằng cách đi từ $1$ theo các cung đang có luồng, mỗi lần lấy một cung chưa dùng, cho tới khi tới $n$; luồng chi phí nhỏ nhất không có chu trình vì chi phí dương, nên cách đi này không lặp. Không đủ $k$ đơn vị thì in $-1$. Ta in các lộ trình theo thứ tự từ điển.

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

const ll N = 505, M = 2005, INF = 1e18;
ll n, m, k, ec, to[M], cap[M], cost[M], d[N], pe[N], inq[N], used[M];
vector<ll> g[N];
vector<vector<ll> > ps;

void addEdge(ll u, ll v, ll c, ll w) {
    to[ec] = v, cap[ec] = c, cost[ec] = w, g[u].push_back(ec++);
    to[ec] = u, cap[ec] = 0, cost[ec] = -w, g[v].push_back(ec++);
}

bool spfa(ll s, ll t) {
    for (ll i = 1; i <= n; i++) d[i] = INF, inq[i] = 0;
    queue<ll> q;
    d[s] = 0;
    q.push(s);
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        inq[u] = 0;
        for (ll e : g[u])
            if (cap[e] > 0 && d[u] + cost[e] < d[to[e]]) {
                d[to[e]] = d[u] + cost[e];
                pe[to[e]] = e;
                if (!inq[to[e]]) inq[to[e]] = 1, q.push(to[e]);
            }
    }
    return d[t] < INF;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> k;
    for (ll i = 1; i <= m; i++) {
        ll a, b;
        cin >> a >> b;
        addEdge(a, b, 1, 1);
    }
    ll flow = 0, ans = 0;
    while (flow < k && spfa(1, n)) {
        ll f = k - flow;
        for (ll v = n; v != 1; v = to[pe[v] ^ 1]) f = min(f, cap[pe[v]]);
        for (ll v = n; v != 1; v = to[pe[v] ^ 1]) {
            cap[pe[v]] -= f;
            cap[pe[v] ^ 1] += f;
        }
        flow += f;
        ans += f * d[n];
    }
    if (flow < k) {
        cout << -1 << '\n';
        return 0;
    }
    for (ll i = 1; i <= k; i++) {
        vector<ll> p;
        ll v = 1;
        p.push_back(v);
        while (v != n) {
            for (ll e : g[v])
                if (e % 2 == 0 && cap[e] == 0 && !used[e]) {
                    used[e] = 1;
                    v = to[e];
                    break;
                }
            p.push_back(v);
        }
        ps.push_back(p);
    }
    sort(ps.begin(), ps.end());
    cout << ans << '\n';
    for (ll i = 0; i < k; i++) {
        cout << ps[i].size() << '\n';
        for (ll v : ps[i]) cout << v << ' ';
        cout << '\n';
    }
}

ChạyInput5 6 2
1 2
2 5
1 3
3 4
4 5
2 3

Output5
3
1 2 5
4
1 3 4 5

Độ phức tạp: SPFA $O(VE)$ mỗi lần và không quá $k$ lần tăng luồng, với $k = 499$, $V = 500$, $E = 2000$ cận trên là $5 \cdot 10^8$ nhưng thực tế chạy nhanh hơn nhiều; phần tách đường tốn $O(k \cdot E)$ nhiều nhất.