Matching

Đường tăng và thuật toán Kuhn

Với một cặp ghép $M$, đường tăng là đường đi xen kẽ cạnh ngoài $M$, cạnh trong $M$, bắt đầu và kết thúc ở hai đỉnh chưa ghép. Đảo trạng thái mọi cạnh trên đường tăng làm $M$ tăng thêm 1. Định lý Berge: $M$ lớn nhất khi và chỉ khi không còn đường tăng.

Kuhn: lần lượt với mỗi đỉnh trái $u$, tìm đường tăng bằng DFS. Thử từng đỉnh phải $v$ kề $u$ chưa thăm trong lượt này: nếu $v$ trống, hoặc đỉnh trái đang ghép với $v$ tìm được chỗ khác, thì ghép $u$ với $v$. Mỗi lượt $O(E)$, tổng $O(VE)$; thực tế chạy nhanh hơn nhiều. Đánh dấu thăm bằng số hiệu lượt để khỏi xóa mảng.

Ví dụCác Cặp Tương Thích

Đề. $n, m \le 500$ người hai nhóm, $k \le 1000$ cặp tương thích. In số cặp lớn nhất và các cặp.

Lời giải. Thuật toán Kuhn: lần lượt với từng người nhóm trái, tìm một đường tăng bắt đầu từ người đó bằng DFS. Đường tăng đi từ trái sang phải bằng cạnh bất kỳ, từ phải về trái bằng cạnh đang ghép, và kết thúc ở một người phải còn tự do. Đảo trạng thái các cạnh trên đường làm số cặp tăng 1. Theo định lý Berge, khi không còn đường tăng thì cặp ghép là lớn nhất.

Bước 1: tìm đường tăng. mt[v] là người trái đang ghép với người phải $v$. Thử từng $v$ kề $u$: $v$ còn tự do thì ghép luôn; $v$ đã ghép thì thử tìm cho mt[v] một người khác bằng đệ quy. Thành công thì gán mt[v] = u: trên đường về, mọi cạnh của đường tăng được đảo. vis[v] = stamp để mỗi đỉnh phải chỉ được thử một lần trong một lần tìm; dùng số hiệu lần tìm làm dấu thì khỏi xóa mảng vis.

bool kuhn(int u, int stamp) {
    for (int v : g[u])
        if (vis[v] != stamp) {
            vis[v] = stamp;
            if (!mt[v] || kuhn(mt[v], stamp)) {
                mt[v] = u;
                return 1;
            }
        }
    return 0;
}

Bước 2: in. ml[u] dựng lại từ mt để in theo thứ tự người trái.

for (int u = 1; u <= n; u++) res += kuhn(u, u);
for (int v = 1; v <= m; v++)
    if (mt[v]) ml[mt[v]] = v;

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

const int N = 505;
int n, m, k, mt[N], ml[N], vis[N];
vector<int> g[N];

bool kuhn(int u, int stamp) {
    for (int v : g[u])
        if (vis[v] != stamp) {
            vis[v] = stamp;
            if (!mt[v] || kuhn(mt[v], stamp)) {
                mt[v] = u;
                return 1;
            }
        }
    return 0;
}

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

    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }
    int res = 0;
    for (int u = 1; u <= n; u++) res += kuhn(u, u);
    for (int v = 1; v <= m; v++)
        if (mt[v]) ml[mt[v]] = v;
    cout << res << '\n';
    for (int u = 1; u <= n; u++)
        if (ml[u]) cout << u << ' ' << ml[u] << '\n';
}

Input4 4 5
1 1
1 2
2 1
3 3
4 3

Output3
1 2
2 1
3 3

Mỗi lần tìm $O(k)$, có $n$ lần: $O(nk)$.

Định lý König: phủ đỉnh nhỏ nhất

Trên đồ thị hai phía, phủ đỉnh nhỏ nhất (tập đỉnh chạm mọi cạnh) có kích thước bằng cặp ghép lớn nhất. Dựng: từ mọi đỉnh trái chưa ghép, đi theo đường xen kẽ (trái sang phải bằng cạnh bất kỳ, phải sang trái bằng cạnh ghép), đánh dấu các đỉnh tới được. Phủ đỉnh là đỉnh trái không được đánh dấu cùng đỉnh phải được đánh dấu.

Hệ quả hay dùng: tập độc lập lớn nhất $= V - $ cặp ghép lớn nhất; số đường đi rời đỉnh ít nhất phủ một DAG $=$ số đỉnh $-$ cặp ghép lớn nhất trên đồ thị tách đỉnh ra/vào.

Ví dụPhủ Các Ô Được Đánh Dấu

Đề. Bảng $N \times N$, $N \le 100$, có các ô đánh dấu o. Chọn ít hàng và cột nhất sao cho mọi ô đánh dấu nằm trên một hàng hoặc cột được chọn, in các hàng, cột đó.

Lời giải. Mỗi ô đánh dấu $(i, j)$ là một cạnh nối hàng $i$ với cột $j$. Chọn hàng, cột để mọi ô đánh dấu nằm trên một hàng hoặc cột được chọn chính là phủ đỉnh của đồ thị hai phía này. Theo định lý König, phủ đỉnh nhỏ nhất bằng cặp ghép lớn nhất. Tìm cặp ghép bằng Kuhn như ví dụ trước, rồi dựng phủ: đánh dấu mọi đỉnh tới được từ các hàng chưa ghép theo đường xen kẽ, lấy hàng không được đánh dấu và cột được đánh dấu.

Bước 1: đi theo đường xen kẽ. Từ hàng $u$ sang mọi cột kề, từ cột đi tiếp về hàng đang ghép với nó.

void alt(int u) {
    visL[u] = 1;
    for (int v : g[u])
        if (!visR[v]) {
            visR[v] = 1;
            if (mt[v] && !visL[mt[v]]) alt(mt[v]);
        }
}

for (int u = 1; u <= n; u++)
    if (!ml[u]) alt(u);

Bước 2: vì sao là một phủ. Lấy một ô $(i, j)$. Nếu hàng $i$ không được đánh dấu thì nó được chọn. Nếu hàng $i$ được đánh dấu thì alt đã đi qua cạnh $(i, j)$ nên cột $j$ được đánh dấu và được chọn.

Bước 3: vì sao đúng bằng số cặp. Hàng chưa ghép đều là điểm xuất phát nên đều được đánh dấu, tức hàng được chọn đều đã ghép. Cột được đánh dấu cũng đã ghép, nếu không thì có đường tăng. Một cặp không thể góp cả hai đầu: cột của nó được đánh dấu thì alt đi tiếp về hàng của nó và hàng ấy được đánh dấu. Mỗi cặp góp đúng một đỉnh.

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

const int N = 105;
int n, mt[N], ml[N], vis[N];
bool visL[N], visR[N];
vector<int> g[N];

bool kuhn(int u, int stamp) {
    for (int v : g[u])
        if (vis[v] != stamp) {
            vis[v] = stamp;
            if (!mt[v] || kuhn(mt[v], stamp)) {
                mt[v] = u;
                return 1;
            }
        }
    return 0;
}

void alt(int u) {
    visL[u] = 1;
    for (int v : g[u])
        if (!visR[v]) {
            visR[v] = 1;
            if (mt[v] && !visL[mt[v]]) alt(mt[v]);
        }
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= n; j++)
            if (s[j - 1] == 'o') g[i].push_back(j);
    }
    int res = 0;
    for (int u = 1; u <= n; u++) res += kuhn(u, u);
    for (int v = 1; v <= n; v++)
        if (mt[v]) ml[mt[v]] = v;
    for (int u = 1; u <= n; u++)
        if (!ml[u]) alt(u);
    cout << res << '\n';
    for (int u = 1; u <= n; u++)
        if (!visL[u]) cout << 1 << ' ' << u << '\n';
    for (int v = 1; v <= n; v++)
        if (visR[v]) cout << 2 << ' ' << v << '\n';
}

Input4
.o..
.o.o
...o
.o..

Output2
2 2
2 4

$O(N \cdot N^2)$ cho Kuhn trên tối đa $N^2$ cạnh.

Hopcroft-Karp

Mỗi pha, BFS từ mọi đỉnh trái chưa ghép để chia lớp theo độ dài đường xen kẽ ngắn nhất, rồi DFS chỉ đi theo các lớp tăng dần, tìm một tập cực đại các đường tăng ngắn nhất rời nhau và đảo hết. Sau $O(\sqrt V)$ pha không còn đường tăng; tổng $O(E \sqrt V)$. Trong DFS, đỉnh nào thất bại thì đặt lớp của nó thành vô cùng để pha này không thử lại.

Bảng ô vuông là đồ thị hai phía tự nhiên: tô màu như bàn cờ theo tính chẵn lẻ của $i + j$, mọi cạnh nối hai ô khác màu. Lát domino nhiều nhất là cặp ghép lớn nhất giữa ô đen và ô trắng.

Ví dụLát Domino Tối Đa

Đề. Bảng $H \times W$ ($\le 100 \times 100$) có ô trống và ô chặn. Đặt nhiều domino nhất trên ô trống, in bảng với domino ngang là ><, dọc là v trên ^.

Lời giải. Tô bảng như bàn cờ theo tính chẵn lẻ của $i + j$; mỗi domino phủ đúng một ô mỗi màu, nên số domino lớn nhất là cặp ghép lớn nhất giữa ô trống chẵn và ô trống lẻ kề nhau. Đồ thị tới $10^4$ đỉnh, nên dùng Hopcroft-Karp thay cho Kuhn. Ô $(i, j)$ có số hiệu $iW + j + 1$.

Bước 1: dựng đồ thị. lefts là các ô trống có $i + j$ chẵn; mỗi ô nối với các ô trống kề, đều là ô lẻ.

if (a[i][j] != '.' || (i + j) % 2) continue;
int u = i * w + j + 1;
lefts.push_back(u);
for (int d = 0; d < 4; d++) {
    int x = i + dx[d], y = j + dy[d];
    if (x >= 0 && x < h && y >= 0 && y < w && a[x][y] == '.') g[u].push_back(x * w + y + 1);
}

Bước 2: BFS chia lớp. Ô trái tự do có dist = 0; từ ô trái u sang ô phải v, rồi theo cạnh ghép sang ô trái mr[v] ở lớp kế. Gặp ô phải tự do nghĩa là pha này còn đường tăng.

for (int v : g[u]) {
    int x = mr[v];
    if (!x) found = 1;
    else if (dist[x] == INF) dist[x] = dist[u] + 1, q.push(x);
}

Bước 3: DFS theo lớp. Chỉ đi sang ô trái ở đúng lớp dist[u] + 1, nên mọi đường tìm được trong một pha đều là đường tăng ngắn nhất. Thất bại thì đặt dist[u] = INF để pha này không thử lại $u$. Mỗi pha tìm một tập đường tăng rời nhau; sau $O(\sqrt V)$ pha không còn đường tăng.

bool dfs(int u) {
    for (int v : g[u]) {
        int x = mr[v];
        if (!x || (dist[x] == dist[u] + 1 && dfs(x))) {
            ml[u] = v, mr[v] = u;
            return 1;
        }
    }
    dist[u] = INF;
    return 0;
}

Bước 4: vẽ. Hai ô cùng hàng là domino ngang, ô trái nhận >, ô phải <; cùng cột là domino dọc, ô trên v, ô dưới ^.

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

const int N = 1e4 + 5, INF = 1e9;
int h, w, ml[N], mr[N], dist[N];
vector<int> g[N], lefts;
string a[105];

bool bfs() {
    queue<int> q;
    for (int u : lefts) {
        if (!ml[u]) dist[u] = 0, q.push(u);
        else dist[u] = INF;
    }
    bool found = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            int x = mr[v];
            if (!x) found = 1;
            else if (dist[x] == INF) dist[x] = dist[u] + 1, q.push(x);
        }
    }
    return found;
}

bool dfs(int u) {
    for (int v : g[u]) {
        int x = mr[v];
        if (!x || (dist[x] == dist[u] + 1 && dfs(x))) {
            ml[u] = v, mr[v] = u;
            return 1;
        }
    }
    dist[u] = INF;
    return 0;
}

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

    cin >> h >> w;
    for (int i = 0; i < h; i++) cin >> a[i];
    int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++) {
            if (a[i][j] != '.' || (i + j) % 2) continue;
            int u = i * w + j + 1;
            lefts.push_back(u);
            for (int d = 0; d < 4; d++) {
                int x = i + dx[d], y = j + dy[d];
                if (x >= 0 && x < h && y >= 0 && y < w && a[x][y] == '.') g[u].push_back(x * w + y + 1);
            }
        }
    int res = 0;
    while (bfs())
        for (int u : lefts)
            if (!ml[u] && dfs(u)) res++;
    for (int u : lefts)
        if (ml[u]) {
            int i = (u - 1) / w, j = (u - 1) % w, x = (ml[u] - 1) / w, y = (ml[u] - 1) % w;
            if (i == x) {
                a[i][min(j, y)] = '>';
                a[i][max(j, y)] = '<';
            } else {
                a[min(i, x)][j] = 'v';
                a[max(i, x)][j] = '^';
            }
        }
    cout << res << '\n';
    for (int i = 0; i < h; i++) cout << a[i] << '\n';
}

Input2 2
..
..

Output2
><
><

$O(E \sqrt V)$.

Ghép có trọng số: thuật toán Hungary

Bài phân công: ma trận chi phí $n \times n$, chọn một hoán vị có tổng nhỏ nhất. Thuật toán Hungary giữ thế vị $u_i$ cho hàng, $v_j$ cho cột với $u_i + v_j \le c_{ij}$, chỉ ghép trên các cạnh “chặt” $u_i + v_j = c_{ij}$. Lần lượt thêm từng hàng; khi không tìm được đường tăng trên cạnh chặt, tăng thế vị một lượng $\Delta$ nhỏ nhất để có thêm cạnh chặt, như một bước Dijkstra. Mỗi hàng $O(n^2)$, tổng $O(n^3)$. Tổng chi phí tối ưu bằng $-v_0$ trong cách cài với cột ảo 0.

Muốn cực đại thì đổi dấu chi phí. Ma trận chữ nhật $n \le m$ chạy được ngay, mỗi hàng ghép một cột.

Ví dụPhân Công Chi Phí Nhỏ Nhất

Đề. $n \le 200$ nhân viên, $n$ công việc, chi phí $c_{ij} \le 1000$. Giao mỗi người một việc khác nhau, tổng chi phí nhỏ nhất, in tổng và phương án.

Lời giải. Thuật toán Hungary giữ thế vị $u_i$ cho hàng, $v_j$ cho cột với $u_i + v_j \le c_{ij}$ mọi lúc. Tổng thế vị là cận dưới của mọi phương án, và khi mọi cặp ghép đều nằm trên cạnh chặt ($u_i + v_j = c_{ij}$) thì cặp ghép đạt đúng cận đó, nên tối ưu. Thêm lần lượt từng hàng: tìm đường tăng chỉ đi trên cạnh chặt; chưa tới được cột tự do thì tăng thế vị một lượng nhỏ nhất để có thêm cạnh chặt. Cột ảo 0 làm điểm xuất phát, p[j] là hàng ghép với cột $j$, way[j] là cột đứng trước $j$ trên đường tăng.

Bước 1: mở rộng cây tìm kiếm. Đầu mỗi lượt p[0] = i đặt hàng mới vào cột ảo, used là các cột đã thuộc cây. Hàng i0 vừa được thêm cập nhật minv[j], chi phí rút gọn nhỏ nhất để đi tới cột $j$ chưa dùng, và ghi way[j]. delta là giá trị nhỏ nhất trong các minv, ứng với cột j1.

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;
    }

Bước 2: cập nhật thế vị. Cột đã dùng giảm v, hàng của chúng tăng u cùng một lượng, nên cạnh chặt trong cây vẫn chặt; minv của cột chưa dùng giảm delta, và cột j1 có cạnh chặt mới. Đi sang j1; nếu j1 tự do thì dừng.

for (int j = 0; j <= n; j++) {
    if (used[j]) u[p[j]] += delta, v[j] -= delta;
    else minv[j] -= delta;
}
j0 = j1;

Bước 3: đảo đường tăng. Đi ngược theo way, dời mỗi hàng sang cột kế tiếp trên đường.

do {
    int j1 = way[j0];
    p[j0] = p[j1];
    j0 = j1;
} while (j0);

Tổng chi phí là -v[0]: cột ảo gom toàn bộ lượng tăng thế vị của các lượt.

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

const int N = 205;
const ll INF = 1e18;
int n, p[N], way[N], ans[N];
ll a[N][N], u[N], v[N], minv[N];
bool used[N];

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

    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> a[i][j];
    for (int i = 1; i <= n; i++) {
        p[0] = i;
        int j0 = 0;
        for (int j = 0; j <= n; j++) minv[j] = INF, used[j] = 0;
        do {
            used[j0] = 1;
            int i0 = p[j0], j1 = 0;
            ll delta = INF;
            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]);
        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0);
    }
    for (int j = 1; j <= n; j++) ans[p[j]] = j;
    cout << -v[0] << '\n';
    for (int i = 1; i <= n; i++) cout << i << ' ' << ans[i] << '\n';
}

Input3
9 2 7
6 4 3
5 8 1

Output9
1 2
2 1
3 3

Mỗi lượt $O(n^2)$, tổng $O(n^3)$.

Ghép ổn định

Mỗi người hai phía xếp hạng toàn bộ phía kia. Cặp ghép hoàn hảo là ổn định nếu không có hai người khác cặp cùng thích nhau hơn người đang ghép. Gale-Shapley: mỗi người phía $A$ còn tự do cầu hôn người kế tiếp trong danh sách của mình; người phía $B$ giữ lời cầu hôn tốt nhất từng nhận, trả lại người cũ khi có người tốt hơn. Mỗi người $A$ cầu hôn mỗi người $B$ tối đa một lần, nên tổng $O(n^2)$, và kết quả luôn ổn định: nếu $A_i$ thích $B_j$ hơn bạn ghép thì $A_i$ đã từng cầu hôn $B_j$ và bị từ chối vì $B_j$ có người tốt hơn.

Kết quả là phương án tốt nhất cho phía chủ động cầu hôn trong mọi ghép ổn định.

Ví dụGhép Cặp Ổn Định

Đề. $t \le 100$ bộ, mỗi bộ $n \le 500$ người mỗi phía; danh sách ưu tiên của phía $B$ cho trước, rồi của phía $A$, mỗi dòng mở đầu bằng số hiệu người. In một ghép ổn định.

Lời giải. Gale-Shapley với phía $A$ cầu hôn. Mỗi người $A$ còn tự do cầu hôn người kế tiếp trong danh sách của mình; người $B$ giữ lời cầu hôn tốt nhất từng nhận và trả lại người cũ khi có người tốt hơn.

Bước 1: bảng hạng. Để $B$ so hai người trong $O(1)$, danh sách của $B$ ghi thẳng thành hạng rk[b][a]; danh sách của $A$ giữ nguyên thứ tự trong pa. Mỗi dòng mở đầu bằng số hiệu người.

for (int r = 0; r < n; r++) {
    int a;
    cin >> a;
    rk[b][a] = r;
}

Bước 2: vòng cầu hôn. Hàng đợi fr chứa người $A$ đang tự do; nxt[a] là vị trí kế tiếp trong danh sách của $a$. $b$ chưa có ai thì nhận $a$; có người cũ mà thích $a$ hơn thì đổi và đẩy người cũ vào lại hàng đợi; ngược lại $a$ bị từ chối, quay lại hàng đợi để cầu hôn người kế. Mỗi người $A$ cầu hôn mỗi người $B$ tối đa một lần, nên vòng lặp chạy không quá $n^2$ lần.

while (!fr.empty()) {
    int a = fr.front();
    fr.pop();
    int b = pa[a][nxt[a]++];
    if (!husband[b]) husband[b] = a;
    else if (rk[b][a] < rk[b][husband[b]]) fr.push(husband[b]), husband[b] = a;
    else fr.push(a);
}

Vì sao ổn định: nếu $a$ thích $b$ hơn vợ hiện tại thì $a$ đã cầu hôn $b$ trước, và bị từ chối hoặc bị trả lại vì $b$ có người tốt hơn. Lựa chọn của $b$ chỉ tốt lên theo thời gian, nên $b$ không thích $a$ hơn chồng hiện tại. Mỗi bộ dữ liệu đặt lại nxt và husband.

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

const int N = 505;
int n, pa[N][N], rk[N][N], nxt[N], husband[N], wife[N];

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

    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int k = 0; k < n; k++) {
            int b;
            cin >> b;
            for (int r = 0; r < n; r++) {
                int a;
                cin >> a;
                rk[b][a] = r;
            }
        }
        for (int k = 0; k < n; k++) {
            int a;
            cin >> a;
            for (int r = 0; r < n; r++) cin >> pa[a][r];
        }
        queue<int> fr;
        for (int a = 1; a <= n; a++) nxt[a] = 0, husband[a] = 0, fr.push(a);
        while (!fr.empty()) {
            int a = fr.front();
            fr.pop();
            int b = pa[a][nxt[a]++];
            if (!husband[b]) husband[b] = a;
            else if (rk[b][a] < rk[b][husband[b]]) fr.push(husband[b]), husband[b] = a;
            else fr.push(a);
        }
        for (int b = 1; b <= n; b++) wife[husband[b]] = b;
        for (int a = 1; a <= n; a++) cout << a << ' ' << wife[a] << '\n';
    }
}

Input1
3
1 2 1 3
2 1 2 3
3 1 2 3
1 1 2 3
2 1 2 3
3 2 3 1

Output1 2
2 1
3 3

Mỗi bộ $O(n^2)$.