数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究在 C++ 中找到与 X 绝对差最大的结点
假设我们有一棵树，以及所有节点的权重和一个整数 x。我们必须找到节点 i，使得 |weight[i] - x| 最小。如果该图如下，且 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
更新时间： 17-Dec-2019
70 次浏览
广告