資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告