Xとの絶対差がC++で最大値を与えるノードを見つけます

ツリーがあり、すべてのノードの重みと整数xがあるとします。 | weight [i]--x|となるようなノードiを見つける必要があります。最小です。グラフが以下のようで、x =15

出力は3になります。ノードごとに次のようになります

ノード1、| 5 – 15 | =10

ノード2、| 10 – 15 | =5

ノード3、| 11 – 15 | =4

ノード4、| 8 – 15 | =7

ノード5、| 6 – 15 | =9

アイデアは単純です。ツリーでDFSを実行し、ノードの追跡を行います。ノードのxとの重み付き絶対差が最小値を示します

例

#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;
}

出力

The node number is: 3