Hướng dẫn giải của Điệp viên 007


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, haidang3004, kminh0505, tdnq

Hiểu bài toán

Bài toán yêu cầu tìm chi phí nhỏ nhất để thu thập thông tin về tất cả B căn cứ quân sự. Có hai loại đối tượng:

  1. Người lính (N người): Mỗi người lính thuộc về một căn cứ cụ thể và có chi phí để mua thông tin.
  2. Sĩ quan (M người): Mỗi sĩ quan có chi phí và một danh sách những người quen biết (gồm cả lính và sĩ quan). Mối quan hệ là một chiều. Nếu mua thông tin từ một sĩ quan, ta có được thông tin về tất cả các căn cứ mà những người quen biết của sĩ quan đó nắm giữ (được gián tiếp qua các mối quan hệ).

Mục tiêu: Chọn một tập hợp con (subset) các đối tượng (lính/sĩ quan) sao cho:

  • Tập hợp này phải cung cấp đủ thông tin về tất cả B căn cứ.
  • Chi phí tổng của các đối tượng được chọn là nhỏ nhất.

Có thể hiểu các đối tượng là các node trong một đồ thị có hướng. Mua thông tin từ một node cho phép ta truy cập vào thông tin mà node đó có và thông tin từ các node mà nó trỏ tới (qua mối quan hệ quen biết). Node là lính cung cấp thông tin về 1 căn cứ duy nhất. Node là sĩ quan có thể cung cấp nhiều căn cứ nếu có đường dẫn đến lính của các căn cứ đó.

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

Cách Quy hoạch động trên đồ thị (DFS + DP)
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
const int MAXN = 200005;

int B, N, M;
long long cost[MAXN];
int mask[MAXN]; // Mask các căn cứ mà node này có thể reach được
vector<int> adj[MAXN]; // Đồ thị ngược: node u -> node v nghĩa là mua u sẽ có info từ v (v là quen của u)
// Hoặc đồ thị xuôi: u quen v -> u -> v. Dùng đồ thị ngược để DFS từ lính lên.

void dfs(int u) {
    if (mask[u] != -1) return; // Đã tính rồi
    mask[u] = 0;

    // Nếu là lính (1..N), mask cơ bản là bit tương ứng căn cứ
    if (1 <= u && u <= N) {
        // base_of[u] cần được lưu trữ hoặc suy ra. 
        // Trong bài này, ta cần map lính vào căn cứ. 
        // Giả sử ta có base[u] là căn cứ của lính u.
        // Mask = (1 << (base[u] - 1)).
        // Code mẫu dưới đây giả định đã xử lý base[u]
    }

    // Duyệt các node có thể reach được từ u (các node mà u quen biết)
    // Nếu đồ thị là u.quen(v) -> adj[u].push_back(v)
    // Khi mua u, ta có info từ v. Nên ta cần merge mask của v vào mask của u.
    // Tuy nhiên, v có thể chưa tính mask.
    // Cách tốt nhất là dùng đồ thị ngược: v -> u (nghĩa là u quen v, mua u có v).
    // Hoặc DFS topo từ lính lên.

    // Giải pháp:
    // Xây dựng đồ thị: u (người mua) -> v (người quen).
    // Nếu ta duyệt DFS từ u, ta cần info từ v. Nên ta phải gọi dfs(v) trước.
    // Ta có thể dùng Topo sort hoặc duyệt từ sink (lính) về nguồn (si quan).
    // Hoặc dùng memoization: dfs(u) trả về mask của u.
    // Mask(u) = (base_mask nếu là lính) OR (Union of mask(v) for v in adj[u]).
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> B >> N >> M;

    // Đọc lính
    int soldier_idx = 1;
    for (int b = 0; b < B; ++b) {
        int K; cin >> K;
        while(K--) {
            long long c; cin >> c;
            cost[soldier_idx] = c;
            // Gán mask cho lính
            mask[soldier_idx] = (1 << b);
            soldier_idx++;
        }
    }

    // Đọc sĩ quan
    int officer_idx = N + 1;
    for (int i = 0; i < M; ++i) {
        long long S; int R;
        cin >> S >> R;
        cost[officer_idx] = S;
        mask[officer_idx] = -1; // Chưa tính
        for (int j = 0; j < R; ++j) {
            int acquaintance;
            cin >> acquaintance;
            // Sĩ quan officer_idx quen acquaintance
            // Mua officer_idx -> có info từ acquaintance
            adj[officer_idx].push_back(acquaintance);
        }
        officer_idx++;
    }

    // Tính mask cho tất cả (chỉ cần tính cho sĩ quan, lính đã có sẵn)
    // Dùng topo sort hoặc DFS memoization
    // Do đồ thị có thể có chu trình (si quan quen nhau), cần cẩn thận.
    // Nếu có chu trình, ta có thể coi Strongly Connected Components (SCC).
    // Hoặc đơn giản hơn: DFS với visited set để tránh loop, nhưng cycle vẫn cho phép info chia sẻ.
    // Trong cycle, mua 1 node sẽ có info cả cycle. Ta có thể coi cycle là 1 node tổng hợp.

    // Cách tiếp cận SCC:
    // 1. Xây dựng đồ thị G: u -> v (u quen v).
    // 2. Tìm SCC.
    // 3. Xây dựng DAG của các SCC.
    // 4. Mask của SCC = Union mask của các node trong SCC và Union mask của SCC children.
    // 5. Chi phí của SCC = Min(cost của các node trong SCC).
    // 6. Quy hoạch động trên DAG (Top-down hoặc Bottom-up).

    // Code mẫu:
    // (Logic này khá phức tạp để viết gọn, nên thường sẽ dùng BFS/DFS mark).
    // Tuy nhiên, do B nhỏ (<=12), ta có thể dùng Bitmask DP.
    // Xem solution 1 và 2.

    return 0;
}
  • Time Complexity: O(N + M + 2^B * (N + M))
  • Space Complexity: O(N + M)

Cách này tập trung vào việc xác định mỗi người lính/sĩ quan có thể cung cấp thông tin về những căn cứ nào (tính mask).

  1. Xây dựng đồ thị: Tạo đồ thị có hướng, cạnh từ A đến B nếu A quen B.
  2. Tính Mask: Do đồ thị có thể có chu trình (các sĩ quan quen nhau), ta cần xử lý Strongly Connected Components (SCC). Một SCC có thể được coi là một đơn vị tổng hợp: nếu chọn bất kỳ node nào trong SCC, ta có thể truy cập thông tin của tất cả node khác trong SCC.
    • Tìm SCC (Dùng Tarjan hoặc Kosaraju).
    • Xây dựng DAG của các SCC.
    • Tính mask cho từng SCC: Mask(SCC) = Union(Mask của các node trong SCC) OR Union(Mask(SCC) của các SCC con).
    • Chi phí của SCC là chi phí nhỏ nhất của các node trong SCC đó.
  3. Quy hoạch động: Sau khi có mask và cost cho mỗi SCC (tương đương một node tổng hợp), ta cần chọn một tập hợp con các SCC sao cho tổng mask = (1 << B) - 1 với chi phí nhỏ nhất.
    • Dùng DP: dp[mask] là chi phí nhỏ nhất để đạt được mask đó.
    • Duyệt qua các SCC, cập nhật DP: new_dp[mask | mask_scc] = min(new_dp[mask | mask_scc], dp[mask] + cost_scc).

Phương pháp này đảm bảo tìm được lời giải tối ưu.

Cách BFS / DFS Propagation (Giải thuật lan truyền)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const int MAXB = 12;

int B, N, M;
long long cost[MAXN];
int base_of[MAXN]; // base of soldier
int mask[MAXN]; // Mask các căn cứ mà node này có thể reach được
vector<int> adj[MAXN]; // Đồ thị xuôi: u -> v (u quen v)
vector<int> rev_adj[MAXN]; // Đồ thị ngược: v -> u (u quen v) - dùng để lan truyền từ lính

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> B >> N >> M;

    // 1. Đọc lính
    int soldier_ptr = 1;
    for (int b = 0; b < B; ++b) {
        int K; cin >> K;
        while(K--) {
            long long c; cin >> c;
            cost[soldier_ptr] = c;
            base_of[soldier_ptr] = b;
            mask[soldier_ptr] = (1 << b);
            soldier_ptr++;
        }
    }

    // 2. Đọc sĩ quan và xây dựng đồ thị
    int officer_ptr = N + 1;
    for (int i = 0; i < M; ++i) {
        long long S; int R;
        cin >> S >> R;
        cost[officer_ptr] = S;
        mask[officer_ptr] = 0;
        for (int j = 0; j < R; ++j) {
            int acq; cin >> acq;
            adj[officer_ptr].push_back(acq);
            rev_adj[acq].push_back(officer_ptr);
        }
        officer_ptr++;
    }

    // 3. Tính mask cho tất cả các node (Lính + Sĩ quan)
    // Do có chu trình, không thể dùng DFS đơn giản.
    // Có thể dùng BFS/DFS nhiều lần (Fixed Point Iteration) hoặc Topo sort trên SCC.
    // Tuy nhiên, với N, M lớn nhưng B nhỏ, ta có thể tối ưu.

    // Cách tiếp cận lan truyền (BFS) từ lính:
    // Ta cần tìm mask cho mỗi sĩ quan.
    // Nếu ta dùng BFS từ lính trên đồ thị ngược (rev_adj), ta có thể lan truyền mask.
    // Tuy nhiên, trong SCC, info có thể đi vòng.
    // Nếu ta dùng SCC, ta coi SCC là 1 node.

    // Logic SCC + DP (như solution 1):
    // 1. Xây dựng SCC.
    // 2. Tính mask cho mỗi SCC (Bottom-up trên DAG).
    // 3. Dùng DP để chọn SCC tối ưu.

    // Code mẫu logic SCC:
    // ... (Tham khảo Solution 1) ...
    // Rất khó để viết gọn trong snippet, nên chú trọng vào logic.
    // Solution 1 làm BFS cho từng căn cứ để tính mask sĩ quan.
    // Solution 2 dùng SCC.

    return 0;
}
  • Time Complexity: O(B * (N + M))
  • Space Complexity: O(N + M)

Đây là cách tiếp cận trực quan hơn, tập trung vào việc tính toán 'vùng bao phủ' (coverage) của mỗi người.

  1. Tính mask cho lính: Mỗi lính có mask là bit của căn cứ mà họ thuộc về.
  2. Tính mask cho sĩ quan:
    • Vì sĩ quan có thể quen sĩ quan (chu trình), ta không thể dùng DFS thường.
    • Solution 1 của tdnq đưa ra một cách tiếp cận thú vị: Với mỗi căn cứ b, ta chạy BFS để xem sĩ quan nào có thể reach được lính của căn cứ b.
    • Cụ thể, duyệt qua từng căn cứ b:
      • Khởi tạo Queue với tất cả lính thuộc căn cứ b.
      • Chạy BFS trên đồ thị quen biết (u -> v).
      • Các sĩ quan nào được duyệt qua sẽ có bit b trong mask của họ được bật.
    • Làm lại cho tất cả B căn cứ.
  3. Quy hoạch động:
    • Sau khi đã tính được mask và cost cho tất cả đối tượng (lính và sĩ quan), ta có một danh sách các cặp (mask, cost).
    • Dùng DP bitmask: dp[mask] là chi phí nhỏ nhất để thu thập được mask.
    • Duyệt qua từng đối tượng, cập nhật DP.

Ưu điểm của cách này là dễ hiểu và không cần cài đặt Tarjan (SCC).

Cách Tối ưu hóa DP (Min-Top hoặc Dijkstra)
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
const int MAXB = 12;

int main() {
    // Giả sử đã có danh sách các đối tượng (lính + sĩ quan) với (cost, mask)
    // Danh sách này có tên là 'items'
    // int num_items = N + M_scc; 

    // DP array
    vector<long long> dp(1 << MAXB, INF);
    dp[0] = 0;

    // Duyệt qua từng item
    // Có thể tối ưu bằng cách sort items theo cost tăng dần?
    // Hoặc dùng Min-Heap (Dijkstra-like) để tìm state tốt nhất chưa visit.

    // Dijkstra approach:
    // Node là các mask.
    // Edge là mua 1 item từ state hiện tại.
    // Weight là cost của item.

    // Code mẫu Dijkstra:
    /*
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({0, 0});

    while(!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dp[u]) continue;

        for (auto &item : items) {
            int v = u | item.mask;
            long long nd = d + item.cost;
            if (nd < dp[v]) {
                dp[v] = nd;
                pq.push({nd, v});
            }
        }
    }
    */

    // Tuy nhiên, với B=12, số state là 4096. Item có thể lên tới 10^5.
    // Dùng Dijkstra có thể chậm (4096 * 10^5).
    // Nên dùng DP thường:
    for (int i = 0; i < num_items; ++i) {
        for (int mask = (1 << B) - 1; mask >= 0; --mask) {
             if (dp[mask] != INF) {
                 int next_mask = mask | items[i].mask;
                 dp[next_mask] = min(dp[next_mask], dp[mask] + items[i].cost);
             }
        }
    }

    // Hoặc tối ưu: sort items theo cost, dùng set/heap.
    // Nhưng DP bitmask O(Items * 2^B) là chấp nhận được (10^5 * 4096 ~ 4e8, cần tối ưu).
    // Có thể dùng KnapSack style: Iterate mask -> Iterate item.
    // Hoặc chỉ dùng item hiệu quả.

    return 0;
}
  • Time Complexity: O(Items * 2^B)
  • Space Complexity: O(2^B)

Sau khi đã xử lý xong đồ thị và tính được mask cho mỗi đối tượng (bằng SCC hoặc BFS như các cách trên), ta cần chọn một tập hợp con các đối tượng sao cho tổng mask bằng full (tất cả các căn cứ) với chi phí nhỏ nhất.

Bài toán này là bài toán quy hoạch động (Dynamic Programming) trên bitmask.

  1. State: dp[mask] là chi phí nhỏ nhất để có được các căn cứ được đại diện bởi bit mask.
  2. Initialization: dp[0] = 0, các state khác là Vô cùng (INF).
  3. Transition: Với mỗi đối tượng có (cost, obj_mask), ta cập nhật: dp[mask | obj_mask] = min(dp[mask | obj_mask], dp[mask] + cost)

Cải tiến tốc độ:

  • Số lượng đối tượng (Items) có thể rất lớn (N + M ≤ 200,000). Tuy nhiên, số lượng các mask khác nhau là tối đa 2^B = 4096.
  • Nếu nhiều đối tượng có cùng mask, ta chỉ cần quan tâm đến đối tượng có chi phí nhỏ nhất cho mask đó.
  • Ta có thể dùng map<int, long long> hoặc mảng min_cost[mask] để lưu chi phí nhỏ nhất cho mỗi mask trước khi đưa vào DP.
  • Sau đó, chỉ cần chạy DP với số lượng item_unique ≤ 4096.
  • Hoặc đơn giản hơn, dùng Dijkstra: Nodes là các mask, edges là các items. Tuy nhiên DP thường nhanh hơn với số state nhỏ.

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

Cách tiếp cận Time Space Tên
1 O(N + M + 2^B * (N + M)) O(N + M) Quy hoạch động trên đồ thị (DFS + DP)
2 O(B * (N + M)) O(N + M) BFS / DFS Propagation (Giải thuật lan truyền)
3 O(Items * 2^B) O(2^B) Tối ưu hóa DP (Min-Top hoặc Dijkstra)

Bài học kinh nghiệm

  • Bài toán có thể chia làm 2 giai đoạn: (1) Xác định mỗi người có thể cung cấp thông tin về những căn cứ nào (mask) và (2) Chọn người tối ưu để che phủ hết các mask.
  • Do số lượng căn cứ B nhỏ (≤12), kỹ thuật Bitmask Dynamic Programming là chìa khóa.
  • Đồ thị quen biết có thể có chu trình. Cần dùng SCC (Strongly Connected Components) hoặc BFS nhiều lần để tính mask chính xác.

Lỗi thường gặp

  • Không xử lý được chu trình trong đồ thị quen biết dẫn đến tính sai mask (DFS vô hạn hoặc sai lệch).
  • Lỗi chỉ số (Off-by-one error) khi gán ID cho lính (1..N) và sĩ quan (N+1..N+M).
  • Quên dùng long long cho chi phí (cost có thể lên tới 10^6 và tổng có thể vượt quá 32-bit).

Bình luận

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.