Chương trình đếm số lượng truy vấn đúng trong biểu đồ với đường dẫn có trọng số trong C ++

Giả sử chúng ta có một danh sách cạnh cho một đồ thị vô hướng trong đó mỗi cạnh có các trường [u, v, w], u và v là đỉnh nguồn và đỉnh đích và w là trọng số. Và cũng có một danh sách các truy vấn có cùng dạng [u, v, w]. Điều đó đại diện cho câu hỏi là có tồn tại một đường đi giữa u và v sao cho mỗi cạnh trong đường đi có trọng lượng nhiều nhất là w hay không. Vì vậy, hãy tìm số lượng truy vấn đúng.

Vì vậy, nếu đầu vào giống như các cạnh =[[0, 1, 6], [1, 2, 7], [2, 3, 8], [0, 3, 5]] truy vấn =[[0, 2, 14], [1, 0, 3]]

thì đầu ra sẽ là 1, vì chúng ta có thể đi từ nút 0 đến nút 2 bằng cách đi theo đường này [0, 1, 2] với trọng số 13. Nhưng không có đường dẫn nào từ 1 đến 0 với trọng số cạnh 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm get_parent (), hàm này sẽ nhận x, một mệnh của mảng,
• nếu par [x] không phải là x, thì
  • par [x]:=get_parent (par [x], par)
• trả về mệnh giá [x]
• Từ phương thức chính, hãy làm như sau -
• Xác định một mảng 2D gr
• n:=0
• cho mỗi cạnh t trong các cạnh -
  • n:=tối đa là n, t [0] và t [1]
  • chèn một hàng [t [2], 0, t [0], t [1]] vào gr
• cho mỗi truy vấn t trong các truy vấn -
  • chèn một hàng [t [2], 1, t [0], t [1]] vào gr
• sắp xếp gr
• Xác định mệnh của mảng có kích thước n + 1 và điền bằng -1
• để khởi tạo i:=0, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
  • par [i]:=i
• sz:=kích thước của các truy vấn
• ans:=0
• cho mỗi hàng t tính bằng gr
  • a:=t [2], b:=t [3], tp:=t [1], d:=t [0]
  • px:=get_parent (a, par)
  • py:=get_parent (b, par)
  • nếu tp giống 0, thì -
    • nếu px không bằng py, thì -
      • par [py]:=px
  • Mặt khác
    • nếu px giống py, thì -
      • (tăng a thêm 1)
    • (giảm sz đi 1)
    • nếu sz giống 0, thì -
      • Ra khỏi vòng lặp
• trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
int get_parent(int x, vector<int>& par) {
   if (par[x] != x) {
      par[x] = get_parent(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 t : edges) {
      n = max(n, max(t[0], t[1]));
      gr.push_back({t[2], 0, t[0], t[1]});
   }
   for (auto t : queries) {
      gr.push_back({t[2], 1, t[0], t[1]});
   }
   sort(gr.begin(), gr.end());
   vector<int> par(n + 1, -1);
   for (int i = 0; i <= n; i++) {
      par[i] = i;
   }
   int sz = queries.size();
   int ans = 0;
   for (auto t : gr) {
      int a = t[2];
      int b = t[3];
      int tp = t[1];
      int d = t[0];
      int px = get_parent(a, par);
      int py = get_parent(b, par);
      if (tp == 0) {
         if (px != py) {
            par[py] = px;
         }
      }else {
         if (px == py) {
            ans++;
         }
         sz--;
         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);
}

Đầu vào

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

Đầu ra

1