Hướng giải của Ghép cặp hoán vị
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.
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ả:
Lời giải
Phân tích
Bài toán yêu cầu ghép mỗi phần tử với một số phân biệt từ tập lựa chọn của nó. Đây chính là bài toán tìm bộ ghép lớn nhất trên đồ thị hai phía: phần tử ở bên trái, số ở bên phải.
Thuật toán
- Xây dựng đồ thị hai phía với \(N\) đỉnh trái (các phần tử) và \(maxVal\) đỉnh phải (các số, \(maxVal \le N\)).
- Chạy thuật toán Kuhn tìm bộ ghép lớn nhất.
- Kết quả là số phần tử được ghép tối đa.
Độ phức tạp: \(O(N \cdot K)\).
Mã nguồn C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> adj(n + 1);
int max_val = 0;
for (int i = 1; i <= n; i++) {
int k;
cin >> k;
adj[i].resize(k);
for (int j = 0; j < k; j++) {
cin >> adj[i][j];
if (adj[i][j] > max_val) max_val = adj[i][j];
}
}
vector<int> matchR(max_val + 1, 0);
vector<int> seen(max_val + 1, 0);
int timer = 0;
function<bool(int)> dfs = [&](int u) -> bool {
for (int v : adj[u]) {
if (seen[v] == timer) continue;
seen[v] = timer;
if (matchR[v] == 0 || dfs(matchR[v])) {
matchR[v] = u;
return true;
}
}
return false;
};
int ans = 0;
for (int u = 1; u <= n; u++) {
timer++;
if (dfs(u)) ans++;
}
cout << ans << "\n";
return 0;
}
Nhận xét