Hướng giải của Phân công chi phí thấp nhất

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời giải

Phân tích

Bài toán phân công có trọng số (assignment problem) yêu cầu tìm cách phân \(N\) người vào \(N\) công việc với tổng chi phí nhỏ nhất. Đây là bài toán kinh điển có thể giải bằng thuật toán Hungary (Hungarian algorithm).

Thuật toán

Thuật toán Hungary (phiên bản \(O(N^3)\)):

  1. Khởi tạo các mảng phụ \(u[i]\) và \(v[j]\) bằng 0.
  2. Với mỗi người \(i\), thực hiện:
    • Duyệt các công việc chưa ghép, tìm công việc \(j\) có \(a[i][j] - u[i] - v[j]\) nhỏ nhất.
    • Cập nhật \(u\) và \(v\) tương ứng.
    • Ghép người \(i\) với công việc tìm được.
  3. Kết thúc, tổng chi phí = \(\sum c_{ij}\) với các cặp đã ghép.

Độ phức tạp: \(O(N^3)\).

Mã nguồn C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<ll>> a(n + 1, vector<ll>(n + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    vector<ll> u(n + 1, 0), v(n + 1, 0);
    vector<int> p(n + 1, 0), way(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        p[0] = i;
        int j0 = 0;
        vector<ll> minv(n + 1, LLONG_MAX);
        vector<int> used(n + 1, 0);
        do {
            used[j0] = true;
            int i0 = p[j0];
            ll delta = LLONG_MAX;
            int j1 = 0;
            for (int j = 1; j <= n; j++) {
                if (!used[j]) {
                    ll cur = a[i0][j] - u[i0] - v[j];
                    if (cur < minv[j]) {
                        minv[j] = cur;
                        way[j] = j0;
                    }
                    if (minv[j] < delta) {
                        delta = minv[j];
                        j1 = j;
                    }
                }
            }
            for (int j = 0; j <= n; j++) {
                if (used[j]) {
                    u[p[j]] += delta;
                    v[j] -= delta;
                } else {
                    minv[j] -= delta;
                }
            }
            j0 = j1;
        } while (p[j0] != 0);
        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0 != 0);
    }
    vector<int> assignment(n + 1);
    for (int j = 1; j <= n; j++) {
        assignment[p[j]] = j;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += a[i][assignment[i]];
    }
    cout << ans << "\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.