Wiki › Thuật toán › Luồng mạng (Network Flow) › Thuật toán Hungary (bài toán phân công)

Thuật toán Hungary (bài toán phân công)

Thuật toán Hungary dạng thế năng giải bài toán phân công (cặp ghép hoàn hảo trọng số nhỏ nhất trên đồ thị hai phía đầy đủ) trong O(n^3). Kèm ví dụ chạy tay, chứng minh tối ưu qua chi phí rút gọn và cài đặt C++/Python.

huunguyen huunguyen Updated Tháng 11. 16, 2026 Đọc 15 phút 3 lượt xem

Thuật toán Hungary (Hungarian algorithm, còn gọi là Kuhn-Munkres) giải bài toán phân công (assignment problem): cho ma trận chi phí a kích thước n×m (n≤m), chọn cho mỗi hàng (công nhân) một cột (công việc) khác nhau sao cho tổng chi phí nhỏ nhất. Nói theo ngôn ngữ đồ thị, đây là cặp ghép hoàn hảo trọng số nhỏ nhất trên đồ thị hai phía đầy đủ.

Vét cạn phải thử n! hoán vị, quy hoạch động bitmask tốn O(2n·n) nên chỉ chạy được tới n≈20. Thuật toán Hungary chạy trong O(n2m), tức O(n3) với ma trận vuông, đủ nhanh cho n cỡ 500 trở lên. Đây là công cụ chuẩn mỗi khi bài quy về "ghép mỗi phần tử bên trái với đúng một phần tử bên phải, tối thiểu tổng chi phí", và ma trận chi phí dày (gần như mọi cặp đều được phép).

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

Tham lam không được. Cho mỗi công nhân lần lượt lấy việc rẻ nhất còn trống có thể sai rất nặng: với hai công nhân, chi phí của công nhân 1 cho hai việc là (1,2) và của công nhân 2 là (1,100): công nhân 1 lấy việc 1 (chi phí 1) khiến công nhân 2 phải nhận việc 2 với chi phí 100, trong khi phương án đúng chỉ tốn 2+1=3. Cần một cách "đổi ý" có kiểm soát.

Thế năng (potential). Ta duy trì hai mảng số ui (cho hàng) và vj (cho cột) sao cho với mọi cặp

cij′=aij−ui−vj ≥ 0,

gọi là chi phí rút gọn. Bổ đề then chốt:

Nếu có một phép phân công hoàn chỉnh chỉ dùng các ô có cij′=0 thì phép phân công đó tối ưu.

Chứng minh: với một phép phân công σ bất kỳ, ∑iaiσ(i)=∑iciσ(i)′+∑iui+∑j∈σvj. Với ma trận vuông, mỗi cột xuất hiện đúng một lần nên hai tổng thế năng là hằng số ∑u+∑v chung cho mọi σ. Vì c′≥0, tổng chi phí luôn ≥∑u+∑v, và phép phân công toàn ô 0 đạt đúng giá trị này. (Với n<m, thuật toán bên dưới chỉ làm giảm vj của những cột đã từng được thăm, các cột chưa thăm có vj=0, nên lập luận vẫn đúng.)

Đây chính là đối ngẫu quy hoạch tuyến tính: ∑u+∑v là cận dưới, và thuật toán đẩy cận dưới này lên cho tới khi chạm đáp án.

Thêm từng hàng một. Thuật toán có n pha. Pha i thêm hàng i vào cặp ghép đã có của các hàng 1..i−1 (cặp ghép này luôn chỉ dùng ô 0). Từ hàng mới, ta tìm đường tăng (augmenting path): hàng mới lấy một cột, nếu cột đó đã có chủ thì chủ cũ phải chuyển sang cột khác, cứ thế cho tới khi chạm một cột trống. Ta chỉ được đi trên các ô 0. Khi không còn ô 0 nào để mở rộng, ta dịch thế năng:

  • Gọi δ là chi phí rút gọn nhỏ nhất từ một hàng đã thăm tới một cột chưa thăm.
  • Tăng u của mọi hàng đã thăm thêm δ, giảm v của mọi cột đã thăm đi δ.

Ô giữa hàng đã thăm và cột đã thăm không đổi (+δ−δ), nên các ô 0 trong cây tìm kiếm và trong cặp ghép vẫn là 0. Ô từ hàng đã thăm tới cột chưa thăm giảm đúng δ, nên vẫn ≥0 và có ít nhất một ô mới trở thành 0: cây được mở rộng thêm một cột. Mỗi pha thăm tối đa m cột, rồi lật đường tăng. Thực chất đây là Dijkstra tìm đường tăng ngắn nhất trên chi phí rút gọn, đúng tinh thần của Min Cost Flow nhưng tận dụng cấu trúc ma trận đầy đủ.

Mẹo cài đặt (dạng e-maxx). Thêm một cột ảo 0: đặt hàng mới làm "chủ" của cột 0 (p0=i), như vậy hàng mới cũng chỉ là chủ của một cột đã thăm và mọi bước đều đồng nhất. Mảng minvj lưu chi phí rút gọn nhỏ nhất từ cây tới cột j, wayj lưu cột đứng trước j trên đường tăng. Cuối cùng −v0 chính là tổng chi phí tối ưu.

Ví dụ chạy tay

Ma trận chi phí 3×3 (hàng là công nhân, cột là công việc):

            việc 1   việc 2   việc 3
  người 1:     8        4        7
  người 2:     5        2        3
  người 3:     9        4        8

Tham lam theo hàng: người 1 lấy việc 2 (4), người 2 lấy việc 3 (3), người 3 phải lấy việc 1 (9), tổng 16. Đáp án đúng là 15.

Ban đầu u=v=0. Ta theo dõi từng pha (các bước dưới đây được in ra từ chính đoạn code ở mục Cài đặt):

Pha Bước Đang ở hàng δ Cột chọn Cột đó của ai
1 1 1 4 2 trống: dừng
2 1 2 2 2 người 1
2 2 1 1 3 trống: dừng
3 1 3 5 2 người 1
3 2 1 2 3 người 2
3 3 2 1 1 trống: dừng
  • Pha 1: người 1 vào, ô rẻ nhất là việc 2 (chi phí 4), δ=4, u1=4. Việc 2 trống nên ghép ngay người 1 với việc 2.
  • Pha 2: người 2 vào. Ô rẻ nhất là việc 2 (δ=2) nhưng việc 2 đã thuộc người 1, nên người 1 được đưa vào cây. Sau khi dịch thế năng, chi phí rút gọn nhỏ nhất tới một cột chưa thăm là 1 và đạt tại việc 3, mà giá trị 1 này đến từ chính người 2 (3−2=1; người 1 tới việc 3 cũng chỉ bằng 1, không nhỏ hơn). Việc 3 trống: người 2 nhận việc 3, người 1 giữ nguyên việc 2. Sau pha: u=(5,3,0), v=(0,−1,0), −v0=7=4+3.
  • Pha 3: người 3 vào. Ô rẻ nhất là việc 2 (δ=5), thuộc người 1. Từ người 1, rẻ nhất là việc 3 (δ=2), thuộc người 2. Từ người 2, rẻ nhất là việc 1 (δ=1), trống: dừng. Lần ngược theo way: việc 1 được đi tới từ việc 2 (tức qua người 1), việc 2 được đi tới từ cột ảo (người 3). Vậy đường tăng là người 3 lấy việc 2, người 1 chuyển sang việc 1; người 2 giữ việc 3 (người 2 chỉ là một nhánh được thăm, không nằm trên đường tăng).

Trạng thái cuối cùng sau pha 3:

u=(8,4,8),v=(0,−4,−1),−v0=15.

Ma trận chi phí rút gọn cij′=aij−ui−vj:

            việc 1   việc 2   việc 3
  người 1:    [0]       0        0
  người 2:     1        2       [0]
  người 3:     1       [0]       1

Mọi ô đều ≥0 và cặp ghép (ô trong ngoặc) gồm người 1 làm việc 1, người 2 làm việc 3, người 3 làm việc 2, toàn ô 0. Tổng chi phí thật 8+3+4=15, bằng đúng ∑u+∑v=20−5=15: cận dưới đã chạm đáp án, nên 15 là tối ưu (vét cạn 3!=6 hoán vị cũng cho 15).

Cài đặt

Hàm nhận ma trận chi phí n×m với n≤m (chỉ số từ 0), trả về chi phí nhỏ nhất và cột được giao cho từng hàng. Chi phí có thể âm.

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

// Thuật toán Hungary dạng thế năng, O(n^2 m), yêu cầu n <= m.
// a[i][j] (chỉ số từ 0): chi phí giao hàng i cho cột j.
// Trả về {chi phí nhỏ nhất, ans} với ans[i] = cột được giao cho hàng i.
pair<long long, vector<int>> hungarian(const vector<vector<long long>>& a) {
    int n = a.size(), m = a[0].size();
    const long long INF = LLONG_MAX / 4;
    // u: thế năng hàng, v: thế năng cột; nội bộ dùng chỉ số từ 1, cột 0 là cột ảo
    vector<long long> u(n + 1, 0), v(m + 1, 0), minv(m + 1);
    vector<int> p(m + 1, 0), way(m + 1, 0);  // p[j]: hàng đang ghép với cột j (0 = trống)
    vector<char> used(m + 1);
    for (int i = 1; i <= n; i++) {
        p[0] = i;  // đặt hàng mới vào cột ảo 0 rồi tìm đường tăng từ đó
        int j0 = 0;
        fill(minv.begin(), minv.end(), INF);
        fill(used.begin(), used.end(), 0);
        do {
            used[j0] = 1;
            int i0 = p[j0], j1 = 0;
            long long delta = INF;
            for (int j = 1; j <= m; j++) {
                if (used[j]) continue;
                long long cur = a[i0 - 1][j - 1] - u[i0] - v[j];  // chi phí rút gọn
                if (cur < minv[j]) minv[j] = cur, way[j] = j0;
                if (minv[j] < delta) delta = minv[j], j1 = j;
            }
            // dịch thế năng một lượng delta: cạnh trong cây giữ nguyên chi phí rút gọn 0
            for (int j = 0; j <= m; j++) {
                if (used[j]) u[p[j]] += delta, v[j] -= delta;
                else minv[j] -= delta;
            }
            j0 = j1;
        } while (p[j0] != 0);  // dừng khi chạm cột còn trống
        do {  // lần ngược đường tăng, dịch từng cột sang hàng mới
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0 != 0);
    }
    vector<int> ans(n);
    for (int j = 1; j <= m; j++)
        if (p[j] != 0) ans[p[j] - 1] = j - 1;
    return {-v[0], ans};  // -v[0] đúng bằng tổng chi phí tối ưu
}

int main() {  // đọc n m rồi ma trận n x m, in chi phí và cột của từng hàng
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<long long>> a(n, vector<long long>(m));
    for (auto& r : a)
        for (auto& x : r) cin >> x;
    auto [cost, ans] = hungarian(a);
    cout << cost << "\n";
    for (int i = 0; i < n; i++) cout << ans[i] << (i + 1 < n ? ' ' : '\n');
}
Python
def hungarian(a):
    """Thuật toán Hungary dạng thế năng, O(n^2 m), yêu cầu n <= m.
    a[i][j] (chỉ số từ 0): chi phí giao hàng i cho cột j.
    Trả về (chi phí nhỏ nhất, ans) với ans[i] = cột được giao cho hàng i."""
    n, m = len(a), len(a[0])
    INF = float("inf")
    u = [0] * (n + 1)  # thế năng hàng (chỉ số từ 1)
    v = [0] * (m + 1)  # thế năng cột, cột 0 là cột ảo
    p = [0] * (m + 1)  # p[j]: hàng đang ghép với cột j (0 = trống)
    way = [0] * (m + 1)
    for i in range(1, n + 1):
        p[0] = i  # đặt hàng mới vào cột ảo 0 rồi tìm đường tăng từ đó
        j0 = 0
        minv = [INF] * (m + 1)
        used = [False] * (m + 1)
        while True:
            used[j0] = True
            i0, j1, delta = p[j0], 0, INF
            row, ui = a[i0 - 1], u[i0]
            for j in range(1, m + 1):
                if used[j]:
                    continue
                cur = row[j - 1] - ui - v[j]  # chi phí rút gọn
                if cur < minv[j]:
                    minv[j] = cur
                    way[j] = j0
                if minv[j] < delta:
                    delta = minv[j]
                    j1 = j
            # dịch thế năng một lượng delta: cạnh trong cây giữ nguyên chi phí rút gọn 0
            for j in range(m + 1):
                if used[j]:
                    u[p[j]] += delta
                    v[j] -= delta
                else:
                    minv[j] -= delta
            j0 = j1
            if p[j0] == 0:  # dừng khi chạm cột còn trống
                break
        while j0:  # lần ngược đường tăng, dịch từng cột sang hàng mới
            j1 = way[j0]
            p[j0] = p[j1]
            j0 = j1
    ans = [0] * n
    for j in range(1, m + 1):
        if p[j]:
            ans[p[j] - 1] = j - 1
    return -v[0], ans  # -v[0] đúng bằng tổng chi phí tối ưu


if __name__ == "__main__":
    import sys

    data = sys.stdin.read().split()
    n, m = int(data[0]), int(data[1])
    vals = list(map(int, data[2 : 2 + n * m]))
    a = [vals[i * m : (i + 1) * m] for i in range(n)]
    cost, ans = hungarian(a)
    print(cost)
    print(*ans)

Một số cách dùng thường gặp:

  • Tối đa tổng trọng số: đổi dấu toàn bộ ma trận (aij→−aij), chạy hàm, rồi đổi dấu kết quả.
  • Cặp bị cấm: gán chi phí rất lớn (ví dụ 1012, đủ lớn hơn mọi tổng hợp lệ nhưng không làm tràn long long khi cộng n lần). Nếu kết quả ≥ giá trị đó thì không có phép phân công hợp lệ.
  • Số hàng nhiều hơn số cột: chuyển vị ma trận, hoặc thêm cột ảo chi phí 0 để thành ma trận vuông.

Độ phức tạp

Thao tác Thời gian Bộ nhớ
Vét cạn hoán vị O(n!·n) O(n)
Quy hoạch động bitmask O(2n·n) O(2n)
Thuật toán Hungary O(n2m) O(nm)

Vì sao O(n2m)? Có n pha. Trong pha i, mỗi vòng do thăm thêm đúng một cột; mọi cột được thăm trước cột trống cuối cùng đều đang có chủ, mà chỉ có i−1 cột có chủ, nên pha i có không quá i vòng. Mỗi vòng quét m cột để cập nhật minv và dịch thế năng. Tổng cộng ∑i=1ni·m=O(n2m), với ma trận vuông là O(n3). Với n=500 là khoảng 1.25·108 phép tính đơn giản, chạy dưới 1 giây bằng C++. Bản Python chậm hơn nhiều lần, thoải mái với n≤200.

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

  • Dùng tham lam hoặc ghép cặp không trọng số: chọn việc rẻ nhất cho từng người, hay chạy Bipartite Matching rồi cộng chi phí, đều sai với ví dụ hai hàng (1,2) và (1,100) (cho 101 thay vì 3).
  • INF quá nhỏ hoặc quá lớn: INF dùng cho minv và delta phải lớn hơn mọi chi phí rút gọn có thể có. Chi phí rút gọn có thể vượt maxaij (thế năng âm dần), nên đừng dùng 1e9 khi aij tới 109. Ngược lại dùng LLONG_MAX rồi cộng trừ sẽ tràn số, vì thế code dùng LLONG_MAX / 4.
  • Quên điều kiện n≤m: nếu n>m, vòng do không bao giờ gặp cột trống, j1 giữ giá trị 0 và vòng lặp chạy sai hoặc vô hạn. Chuyển vị ma trận trước.
  • Lẫn chỉ số: bên trong dùng chỉ số từ 1 vì cột 0 là cột ảo, còn ma trận vào dùng chỉ số từ 0. Quên trừ 1 khi đọc a[i0 - 1][j - 1] cho kết quả lệch mà vẫn "trông hợp lý".
  • Không cập nhật minv của cột chưa thăm khi dịch thế năng: bỏ dòng minv[j] -= delta thì các lần chọn delta sau dùng giá trị cũ, thế năng bị dịch sai và kết quả không còn tối ưu. Lỗi này qua được ví dụ nhỏ, nên luôn đối chiếu với vét cạn.
  • Đọc đáp án từ u, v mà quên dấu: tổng chi phí là −v0 (hoặc tính lại ∑iai,ansi cho chắc), không phải ∑u hay v0.

Biến thể / Mở rộng

  • Luồng chi phí nhỏ nhất: bài phân công là trường hợp đặc biệt của Min Cost Flow (nguồn tới mỗi hàng, mỗi hàng tới mỗi cột, mỗi cột tới đích, sức chứa 1). Khi đồ thị thưa, có sức chứa khác 1 hoặc mỗi người nhận nhiều việc, dùng min cost flow. Khi ma trận dày và vuông, Hungary O(n3) gọn và nhanh hơn.
  • Ghép cặp không trọng số: chỉ cần số cặp tối đa thì dùng Bipartite Matching hoặc Hopcroft-Karp. Lưu ý nhiều tài liệu gọi thuật toán Kuhn (DFS tìm đường tăng) là "thuật toán Hungary"; đó là bản không trọng số.
  • Nhiều đơn vị tại một đỉnh: nếu điểm u cần ghép k lần, nhân bản hàng u thành k hàng giống nhau. Đây đúng là cách bài icpc26mnh dựng ma trận.
  • Chi phí từ khoảng cách: thường ma trận được tính trước bằng BFS hoặc Dijkstra từ mỗi điểm nguồn, rồi mới đưa vào Hungary.
  • Phân công tối ưu theo cổ chai (tối thiểu chi phí lớn nhất thay vì tổng): không cần Hungary, chỉ cần tìm kiếm nhị phân ngưỡng kết hợp ghép cặp không trọng số.

Bài tập luyện

  • Gán Công Việc Bitmask (knapbitmask): (Hard) Phân công N≤16 người cho N việc với tổng chi phí nhỏ nhất; đề gợi ý quy hoạch động bitmask nhưng Hungary giải thẳng trong O(N3), tiện để kiểm tra cài đặt.
  • Bài Toán Phân Công (assgn): (Expert) Bài phân công thuần với n≤200, phải in cả cách phân công; quy hoạch động bitmask không còn chạy được, cần đúng thuật toán Hungary.
  • Khôi phục DNA (icpc26mnh): (Expert) Xâu ngắn nhất chứa mọi K-mer cho trước, quy về đường đi Euler trên đồ thị de Bruijn với ít cạnh lặp nhất; bước cuối là ghép các đỉnh thừa cạnh vào với các đỉnh thiếu cạnh vào theo khoảng cách BFS bằng thuật toán Hungary trên ma trận cỡ 17×17.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0