Bipartite Matching (Ghép cặp hai phía)

Bài toán ghép cặp hai phía (bipartite matching): cho đồ thị hai phía $G=(L\cup R,E)$ — tập đỉnh chia thành hai phía $L$ (trái) và $R$ (phải), mọi cạnh nối một đỉnh trái với một đỉnh phải. Một matching là tập cạnh đôi một không chung đỉnh. Ta cần tìm matching cực đại (maximum matching) — nhiều cạnh nhất có thể.

Đây là mô hình của vô số bài thực tế: phân công $n$ người vào $n$ việc, ghép thí sinh với đề, ghép ô bàn cờ... Thuật toán Kuhn (đường tăng luồng / augmenting path) giải bài này trong $O(V·E)$, nhanh hơn nhiều so với thử mọi cách ghép ($O(2^E)$). Với đồ thị lớn hơn dùng Hopcroft–Karp đạt $O(E\sqrt{V})$.

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

Định nghĩa đường tăng (augmenting path) đối với một matching $M$: đường đi xen kẽ bắt đầu từ một đỉnh trái chưa ghép, đi cạnh-ngoài-$M$, rồi cạnh-trong-$M$, ngoài, trong... và kết thúc ở một đỉnh phải chưa ghép.

Ví dụ đường $u_0-v_0-u_1-v_1$ với $u_0$ chưa ghép, $v_0$ đang ghép với $u_1$, $v_1$ chưa ghép. Cạnh $u_0{v}_0$, $u_1{v}_1$ nằm ngoài $M$; cạnh $v_0{u}_1$ nằm trong $M$. Số cạnh-ngoài nhiều hơn số cạnh-trong đúng 1. Nếu ta lật (đảo trạng thái trong/ngoài $M$ mọi cạnh trên đường): các cạnh ngoài trở thành trong, cạnh trong trở thành ngoài. Kết quả vẫn là matching hợp lệ (mỗi đỉnh vẫn thuộc tối đa một cạnh) nhưng kích thước tăng đúng 1.

Trực giác của thuật toán Kuhn: lần lượt xét từng đỉnh trái $u$. Thử tìm một đường tăng xuất phát từ $u$ bằng DFS. Khi đứng ở $u$, ta duyệt các đỉnh phải $v$ kề:

• Nếu $v$ chưa ghép → ghép $u$ với $v$ ngay (đường tăng độ dài 1).
• Nếu $v$ đang ghép với $u^{\prime }=\text{match}[v]$ → thử nhường chỗ: gọi đệ quy tìm cho $u^{\prime }$ một đỉnh phải khác. Nếu $u^{\prime }$ tìm được chỗ mới, $v$ được giải phóng và ta ghép $u$ với $v$.

Vì sao đúng? Có hai mệnh đề cốt lõi:

1. Định lý Berge: matching $M$ là cực đại khi và chỉ khi không tồn tại đường tăng nào đối với $M$. Vì mỗi lần tìm được đường tăng ta tăng được 1 cạnh, cứ tăng đến khi không còn đường tăng thì đạt cực đại.
2. Tính đơn điệu: một đỉnh trái đã được ghép thì trong suốt thuật toán không bao giờ bị bỏ ghép (chỉ có thể đổi sang đỉnh phải khác). Nên khi xét xong $u$, mọi đỉnh trái trước đó vẫn ghép. Vì vậy chỉ cần xét mỗi đỉnh trái đúng một lần là đủ.

Ví dụ chạy tay

Đồ thị hai phía: trái $\{1,2,3\}$, phải $\{a,b,c\}$, các cạnh:

   L        R
   1 ---- a
    \
     \--- b
   2 ---- a
   3 ---- a
    \
     \--- c

Cụ thể: $1:\{a,b\}$, $2:\{a\}$, $3:\{a,c\}$. Ta xét lần lượt $1,2,3$. Ký hiệu match[v] = đỉnh trái đang giữ $v$ (· = trống).

Xét đỉnh 1 — duyệt $a$: $a$ trống → ghép.

match:  a=1   b=·   c=·
ghép:   1-a                       (size = 1)

Xét đỉnh 2 — duyệt $a$: $a$ đang giữ bởi $1$. Thử nhường: DFS($1$) tìm chỗ khác cho $1$ → $1$ duyệt $b$, $b$ trống → $1$ chuyển sang $b$. $a$ được giải phóng, ghép $2$ với $a$.

            đang thử nhường:  2 -> a -> (1) -> b   [b trống => lật]
match:  a=2   b=1   c=·
ghép:   1-b, 2-a                  (size = 2)

Xét đỉnh 3 — duyệt $a$: $a$ giữ bởi $2$. Thử nhường: DFS($2$) → $2$ chỉ kề $a$, mà $a$ đã visited → $2$ không có chỗ khác → nhường thất bại. Quay lại, $3$ duyệt tiếp $c$: $c$ trống → ghép.

            2 không nhường được (chỉ kề a) => 3 thử cạnh khác: c
match:  a=2   b=1   c=3
ghép:   1-b, 2-a, 3-c             (size = 3)

Không còn đỉnh trái nào → matching cực đại = 3 (ghép hết cả ba). Lưu ý mảng visited được reset trước mỗi lần xét đỉnh trái mới, nhưng giữ nguyên trong suốt một lần DFS để tránh lặp vô hạn khi nhường chỗ.

Cài đặt

Quy ước: phía trái đánh số $1..n_{\text{left}}$, phía phải $1..n_{\text{right}}$. match_r[v] = đỉnh trái đang ghép với $v$ (hoặc $-1$). match_l[u] tương tự (tiện truy vết kết quả).

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

const int MAXN = 505;
vector<int> adj[MAXN];           // adj[u] = các đỉnh PHẢI kề đỉnh trái u
int match_l[MAXN], match_r[MAXN];
bool visited[MAXN];              // đánh dấu đỉnh PHẢI đã thăm trong 1 lần DFS
int n_left, n_right;

// Thử tìm đường tăng xuất phát từ đỉnh trái u
bool dfs(int u) {
    for (int v : adj[u]) {
        if (visited[v]) continue;    // tránh lặp vô hạn khi nhường chỗ
        visited[v] = true;
        // v còn trống, HOẶC chủ hiện tại của v nhường được sang chỗ khác
        if (match_r[v] == -1 || dfs(match_r[v])) {
            match_l[u] = v;          // lật cạnh: ghép u với v
            match_r[v] = u;
            return true;
        }
    }
    return false;                    // không tìm được đường tăng từ u
}

int max_matching() {
    fill(match_l, match_l + n_left + 1, -1);
    fill(match_r, match_r + n_right + 1, -1);
    int res = 0;
    for (int u = 1; u <= n_left; u++) {
        fill(visited, visited + n_right + 1, false);  // reset MỖI đỉnh trái
        if (dfs(u)) res++;           // tăng được đúng 1 nếu có đường tăng
    }
    return res;
}

Mô hình hoá bằng luồng cực đại

Maximum bipartite matching chính là max flow trên mạng: thêm nguồn $s$ nối tới mọi đỉnh trái (cạnh sức chứa 1), mọi đỉnh phải nối tới đích $t$ (sức chứa 1), mỗi cạnh gốc hướng trái→phải sức chứa 1. Giá trị luồng cực đại = kích thước matching.

// Giả sử có lớp MaxFlow (Dinic) với add_edge(u, v, cap) và max_flow(s, t)
MaxFlow mf(n_left + n_right + 2);
int s = 0, t = n_left + n_right + 1;
for (int u = 1; u <= n_left; u++)  mf.add_edge(s, u, 1);
for (int v = 1; v <= n_right; v++) mf.add_edge(n_left + v, t, 1);
for (int u = 1; u <= n_left; u++)
    for (int v : adj[u])
        mf.add_edge(u, n_left + v, 1);
int matching = mf.max_flow(s, t);

Dinic trên mạng đơn vị này chạy $O(E\sqrt{V})$ — tương đương Hopcroft–Karp.

Độ phức tạp

• Thời gian Kuhn: vòng ngoài chạy $V_L$ lần. Mỗi lần ta reset visited rồi DFS; một lần DFS thăm mỗi đỉnh phải tối đa một lần nên quét tối đa $O(E)$ cạnh. Tổng $O(V_L·E)$. Với $V,E\le$ vài nghìn (cạnh tới $~{10}^5$) là dư sức trong giới hạn thời gian.
• Bộ nhớ: danh sách kề $O(V+E)$, các mảng match_l, match_r, visited cỡ $O(V)$. Đệ quy DFS sâu tối đa $O(V)$.

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

• Reset visited sai chỗ: phải fill(visited, false) một lần cho mỗi đỉnh trái ở vòng ngoài, KHÔNG reset bên trong dfs. Nếu reset trong dfs (mỗi lần nhường chỗ) sẽ gây đệ quy vô hạn vì hai đỉnh cứ nhường qua lại nhau. Nếu quên reset hoàn toàn, các đỉnh trái sau bị chặn oan → matching thiếu.
• Đánh dấu visited trên phía sai: visited đánh dấu đỉnh phải đã thử trong lần DFS hiện tại. Đánh dấu nhầm đỉnh trái khiến đường tăng không tìm ra.
• Trùng chỉ số hai phía: nếu đỉnh trái và phải dùng chung dải số (ví dụ cùng đánh $1..n$) mà bạn để chung mảng match, một thao tác ghép sẽ ghi đè nhầm. Dùng hai mảng riêng match_l/match_r, hoặc dịch chỉ số phía phải lên (cộng $n_{\text{left}}$).
• Đỉnh cô lập / cạnh trùng: đỉnh không có cạnh nào vẫn phải được xét (DFS trả false, không sao). Cạnh lặp trong adj[u] chỉ làm chậm, không sai, nhưng nên khử trùng khi $E$ lớn.
• Quên đồ thị phải HAI PHÍA: Kuhn chỉ đúng cho đồ thị hai phía. Trên đồ thị tổng quát (có chu trình lẻ) phải dùng Blossom (Edmonds). Đừng áp Kuhn cho matching tổng quát.
• Nhầm với weighted matching: Kuhn tối đa hoá số cạnh, không quan tâm trọng số. Nếu cần tổng trọng số nhỏ/lớn nhất với ghép hoàn hảo, đó là bài toán phân công → dùng Hungarian (Kuhn–Munkres) hoặc min-cost max-flow, khác hẳn.
• Đệ quy quá sâu (Python/C++): với $V$ lớn, DFS đệ quy có thể tràn stack. Tăng giới hạn đệ quy hoặc viết bản khử đệ quy / dùng Hopcroft–Karp.

Biến thể / Mở rộng

• Định lý König (đồ thị hai phía): kích thước matching cực đại bằng kích thước phủ đỉnh nhỏ nhất (minimum vertex cover): $$\text{Maximum Matching}=\text{Minimum Vertex Cover}.$$ Suy ra tập độc lập lớn nhất (maximum independent set): $$\text{Maximum Independent Set}=|V|-\text{Maximum Matching}.$$ Đây là công cụ chứng minh cực mạnh: nhiều bài "chọn nhiều nhất / cấm ít nhất" quy về matching.

• Phủ đường nhỏ nhất trên DAG (minimum path cover): phủ DAG bằng ít đường đỉnh-rời nhất = $V-(\text{matching của đồ thị hai phía tách đôi mỗi đỉnh})$.

• Hopcroft–Karp: cùng kết quả nhưng $O(E\sqrt{V})$, dùng khi $V,E$ lớn.
• Weighted bipartite matching (bài toán phân công): tối ưu tổng chi phí — dùng thuật toán Hungarian $O(n^3)$ hoặc min-cost max-flow.

Bài tập luyện

• Ghép cạnh trên cây (treematch) — (Trung cấp) maximum matching trên cây; cây là đồ thị hai phía, làm quen định nghĩa matching (lời giải tối ưu bằng greedy/DP trên cây).
• Ghép Cặp Tương Thích (compair) — (Trung cấp) ghép cặp tối đa theo ràng buộc tổng giá trị bằng $A$ hoặc $B$; luyện mô hình hoá bài "ghép tối đa".
• Bài Toán Phân Công (assgn) — (Kỳ cựu) ghép hoàn hảo có trọng số (assignment) tối thiểu tổng chi phí; mở rộng có trọng số của matching hai phía, cần Hungarian / min-cost max-flow và truy vết kết quả.
• Ghép Đôi Platinum (pairedup21) — (Chuyên gia) matching cực đại giữa hai loại bò với ràng buộc khoảng cách, tối ưu tổng trọng số phần chưa ghép; bài matching nâng cao kết hợp tham lam/DP.