Hướng giải của Tập phủ cạnh nhỏ 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 yêu cầu tìm tập phủ cạnh (vertex cover) nhỏ nhất trên đồ thị hai phía. Định lý König phát biểu rằng: trong đồ thị hai phía, kích thước tập phủ cạnh nhỏ nhất bằng kích thước bộ ghép lớn nhất.

Thuật toán

  1. Tìm bộ ghép lớn nhất bằng thuật toán Kuhn.
  2. Xây dựng đồ thị có hướng từ đồ thị gốc: cạnh không thuộc bộ ghép đi từ trái sang phải, cạnh thuộc bộ ghép đi từ phải sang trái.
  3. DFS từ các đỉnh trái chưa được ghép.
  4. Tập phủ cạnh nhỏ nhất gồm: các đỉnh trái không được thăm + các đỉnh phải được thăm.

Độ 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_left, n_right, m;
    cin >> n_left >> n_right >> m;
    vector<vector<int>> adj(n_left + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    vector<int> matchR(n_right + 1, 0);
    vector<int> matchL(n_left + 1, 0);
    vector<int> seen(n_right + 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;
                matchL[u] = v;
                return true;
            }
        }
        return false;
    };
    for (int u = 1; u <= n_left; u++) {
        timer++;
        dfs(u);
    }
    int total = n_left + n_right;
    vector<vector<int>> g(total + 1);
    for (int u = 1; u <= n_left; u++) {
        for (int v : adj[u]) {
            if (matchL[u] == v) {
                g[n_left + v].push_back(u);
            } else {
                g[u].push_back(n_left + v);
            }
        }
    }
    vector<bool> vis(total + 1, false);
    function<void(int)> dfs2 = [&](int u) {
        vis[u] = true;
        for (int v : g[u]) {
            if (!vis[v]) dfs2(v);
        }
    };
    for (int u = 1; u <= n_left; u++) {
        if (matchL[u] == 0 && !vis[u]) dfs2(u);
    }
    int ans = 0;
    for (int u = 1; u <= n_left; u++) {
        if (!vis[u]) ans++;
    }
    for (int v = 1; v <= n_right; v++) {
        if (vis[n_left + v]) ans++;
    }
    cout << ans << "\n";
    return 0;
}

Nhận xét

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