Chương trình đếm truy vấn đúng về đường đi trọng số trong đồ thị C++

Mô tả bài toán

Cho đồ thị vô hướng có trọng số (cạnh [u,v,w]) và danh sách truy vấn [u,v,w]. Mỗi truy vấn hỏi: có đường đi từ u đến v sao cho mọi cạnh trên đường đi có trọng số ≤ w? Đếm số truy vấn đúng.

Ví dụ: edges = [[0,1,6],[1,2,7],[2,3,8],[0,3,5]], queries = [[0,2,14],[1,0,3]] → 1 (chỉ truy vấn đầu đúng).

Giải thuật (Union-Find offline)

1. Gộp edges và queries vào một mảng, đánh dấu type (0=edge, 1=query), sắp xếp theo w tăng dần.
2. Khởi tạo DSU (Disjoint Set Union).
3. Duyệt mảng đã sắp xếp:
   • Nếu type=0: union(u,v).
   • Nếu type=1: nếu find(u)==find(v) thì truy vấn đúng, đếm++.

Ví dụ minh họa (C++)

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

int findParent(int x, vector<int>& par) {
    if (par[x] != x) par[x] = findParent(par[x], par);
    return par[x];
}

int solve(vector<vector<int>>& edges, vector<vector<int>>& queries) {
    vector<vector<int>> gr;
    int n = 0;
    for (auto& e : edges) {
        n = max(n, max(e[0], e[1]));
        gr.push_back({e[2], 0, e[0], e[1]});
    }
    for (auto& q : queries) gr.push_back({q[2], 1, q[0], q[1]});
    sort(gr.begin(), gr.end());
    vector<int> par(n+1);
    iota(par.begin(), par.end(), 0);
    int ans = 0, sz = queries.size();
    for (auto& t : gr) {
        int w = t[0], type = t[1], u = t[2], v = t[3];
        int pu = findParent(u, par), pv = findParent(v, par);
        if (type == 0) {
            if (pu != pv) par[pv] = pu;
        } else {
            if (pu == pv) ans++;
            if (--sz == 0) break;
        }
    }
    return ans;
}

int main() {
    vector<vector<int>> edges = {{0,1,6},{1,2,7},{2,3,8},{0,3,5}};
    vector<vector<int>> queries = {{0,2,14},{1,0,3}};
    cout << solve(edges, queries);
    return 0;
}

Đầu vào

{{0,1,6},{1,2,7},{2,3,8},{0,3,5}}, {{0,2,14},{1,0,3}}

Đầu ra

1