Tìm nút có sự khác biệt tuyệt đối với X cho giá trị lớn nhất trong C ++

Giả sử chúng ta có một cây, trọng số của tất cả các nút và một số nguyên x. Chúng ta phải tìm nút i sao cho | weight [i] - x | là tối thiểu. Nếu biểu đồ như dưới đây và x =15

Đầu ra sẽ là 3. Bây giờ đối với các nút khác nhau, nó sẽ giống như bên dưới

Nút 1, | 5 - 15 | =10

Nút 2, | 10 - 15 | =5

Nút 3, | 11 - 15 | =4

Nút 4, | 8 - 15 | =7

Nút 5, | 6 - 15 | =9

Ý tưởng là đơn giản. Chúng tôi sẽ thực hiện DFS trên cây và theo dõi nút có hiệu số tuyệt đối có trọng số với x cho giá trị nhỏ nhất

Ví dụ

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int min_value = INT_MAX, x, result;
vector<int> graph[100];
vector<int> weight(100);
void dfs(int node, int parent) {
   if (min_value > abs(weight[node] - x)) {
      min_value = abs(weight[node] - x);
      result = node;
   }
   for (int to : graph[node]) {
      if (to == parent)
      continue;
      dfs(to, node);
   }
}
int main() {
   x = 15;
   weight[1] = 5;
   weight[2] = 10;
   weight[3] = 11;
   weight[4] = 8;
   weight[5] = 6;
   graph[1].push_back(2);
   graph[2].push_back(3);
   graph[2].push_back(4);
   graph[1].push_back(5);
   dfs(1, 1);
   cout << "The node number is: " << result;
}

Đầu ra

The node number is: 3