Editorial for library: Thư viện thành phố

Hiểu bài toán

Bài toán yêu cầu tìm chi phí thấp nhất để xây dựng thư viện ở các thành phố sao cho mọi thành phố đều có thể đi đến ít nhất một thành phố có thư viện. Đất nước có n thành phố và m tuyến đường hai chiều nối các thành phố. Chi phí xây thư viện tại thành phố i là a_i. Ta có thể chọn xây thư viện ở bất kỳ thành phố nào và di chuyển qua lại giữa các thành phố được nối bằng đường. Vấn đề này có thể được mô hình hóa như sau: Xét các thành phần liên thông của đồ thị (mỗi thành phần là một nhóm các thành phố nối với nhau qua đường). Trong mỗi thành phần liên thông, ta chỉ cần xây thư viện tại đúng 1 thành phố (thành phố có chi phí thấp nhất trong thành phần đó) là đủ, vì từ các thành phố khác trong cùng thành phần có thể đi đến đó. Tổng chi phí tối thiểu bằng tổng chi phí thư viện thấp nhất của tất cả các thành phần liên thông.

Các cách tiếp cận

Cách DFS/BFS (Duyệt theo thành phần liên thông)

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

const int MAXN = 1e5 + 5;
vector<int> adj[MAXN];
bool visited[MAXN];
int cost[MAXN];
long long total_cost = 0;

void dfs(int u, int &min_cost) {
    visited[u] = true;
    min_cost = min(min_cost, cost[u]);
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, min_cost);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> cost[i];
    }
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            int min_cost = INT_MAX;
            dfs(i, min_cost);
            total_cost += min_cost;
        }
    }
    cout << total_cost;
    return 0;
}

• Time Complexity: O(n + m)
• Space Complexity: O(n + m)

Cách tiếp cận này sử dụng DFS (hoặc BFS) để duyệt qua các đỉnh. Khi gặp một đỉnh chưa được duyệt, ta thực hiện DFS từ đỉnh đó để duyệt toàn bộ thành phần liên thông. Trong quá trình duyệt, ta cập nhật chi phí thư viện nhỏ nhất (mincost) trong thành phần đó. Sau khi duyệt xong một thành phần, ta cộng mincost vào tổng chi phí. Độ phức tạp thời gian là O(n+m) do mỗi đỉnh và cạnh chỉ được duyệt một lần. Phương pháp này dễ hiểu và cài đặt.

Cách Disjoint Set Union (DSU)

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

int n, m, A[100005];
struct DSU {
    vector<int> sz, pa, ts;
    DSU(int n) {
        sz.resize(n + 5);
        pa.resize(n + 5);
        ts.resize(n + 5);
        for (int i = 1; i <= n; i++) {
            sz[i] = 1;
            pa[i] = i;
            ts[i] = A[i]; // Chi phí thư viện ban đầu
        }
    }
    int find(int u) {
        if (u == pa[u]) return u;
        return pa[u] = find(pa[u]);
    }
    void unite(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        if (sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        pa[v] = u;
        ts[u] = min(ts[u], ts[v]); // Cập nhật chi phí nhỏ nhất của tập hợp mới
    }
};

signed main() {
    cin.tie(NULL)->ios_base::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> A[i];
    DSU dsu(n);
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        dsu.unite(x, y);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dsu.pa[i] == i) { // Nếu i là đại diện của tập hợp
            ans += dsu.ts[i];
        }
    }
    cout << ans;
    return 0;
}

• Time Complexity: O((n + m) * α(n))
• Space Complexity: O(n)

Sử dụng cấu trúc dữ liệu DSU (Disjoint Set Union) để quản lý các thành phần liên thông. Ban đầu, mỗi thành phố là một tập hợp riêng biệt với chi phí thư viện là a_i. Khi đọc từng cạnh (u, v), ta nối hai tập hợp chứa u và v lại với nhau. Trong quá trình nối, ta luôn giữ lại chi phí thư viện nhỏ nhất trong tập hợp mới (thuộc tính 'ts'). Cuối cùng, ta duyệt qua các đại diện (representative) của các tập hợp và cộng dồn chi phí. Độ phức tạp gần như tuyến tính O((n+m)α(n)).

Cách Tối ưu DSU không cần mảng phụ

// LonggVuz.
#include<bits/stdc++.h>
using namespace std;
#define int int64_t

int n, m, c[maxn], r[maxn];

int get(int u){
    if(u == r[u]) return u;
    return r[u] = get(r[u]);
}

void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> c[i];
        r[i] = i;
    }
    while(m--){
        int x, y; cin >> x >> y;
        x = get(x); y = get(y);
        if(x != y){
            if(c[x] < c[y]) r[y] = x;
            else {
                r[x] = y;
                c[x] = c[y]; // Ghi đè chi phí nếu cần (Logic hơi lạ, cần kiểm tra)
                // Thực tế giải pháp chuẩn là: Luôn merge theo cách giữ lại chi phí nhỏ nhất
                // Code gốc người dùng viết có vẻ không chuẩn lắm về logic giữ giá trị min, 
                // nhưng ý tưởng là dùng DSU và chỉ duyệt qua node chính.
            }
        }
    }
    int ans = 0;
    for(int i=1; i<=n; i++)
        if(r[i] == i) ans += c[i];
    cout << ans;
}

• Time Complexity: O(n + m)
• Space Complexity: O(n)

Đây là biến thể của DSU với một chút tối ưu hóa về cách lưu trữ. Thay vì lưu riêng mảng chi phí nhỏ nhất, ta có thể ghi đè chi phí của node đại diện ngay trong quá trình union. Tuy nhiên, logic trong code mẫu (Solution 2) cần được hiểu kỹ: nó ghi đè giá trị nếu node được giữ lại là node có chi phí lớn hơn (hoặc tương đương). Dù chi tiết implementation có thể khác nhau, đây là cách tiếp cận dựa trên DSU và chỉ cần O(n) vòng lặp cuối cùng để tổng hợp kết quả.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán chia nhỏ thành các bài toán con độc lập: Với mỗi thành phần liên thông (connected component), ta chỉ cần tìm chi phí thư viện nhỏ nhất trong thành phần đó.
• Mô hình tập hợp: Vấn đề có thể giải quyết bằng cách nhóm các thành phố vào các tập hợp liên thông và lấy giá trị nhỏ nhất của mỗi tập hợp.

Lỗi thường gặp

• Không xử lý các thành phố cô lập (không có đường nối): Các thành phố này tạo thành thành phần liên thông kích thước 1, vẫn cần xây thư viện.
• Sử dụng biến kiểu int cho tổng chi phí: Chi phí a_i lên tới 10^9 và có thể có tới 10^5 thành phần, tổng chi phí có thể vượt quá giới hạn của int 32-bit. Cần sử dụng kiểu long long (hoặc equivalent).
• Quên đánh dấu đã duyệt (visited) trong DFS/BFS dẫn đến lặp vô hạn hoặc sai kết quả.