3511. 路由最大耗时路径

题目描述

假设存在一个二叉树型的路由器网络，经过每个路由器会有耗时。由于我们要对网络进行优化，需要找出这个树型路由器网络中的最大耗时的两个节点间的路径。

路径被定义为一条从任意节点出发，达到任意节点的序列，同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

耗时是路径中各路由器节点值的总和。

第一行一个数n（1≤n≤16383），表示路由器网络的节点数。第二行是完全二叉树的数组表示形式，0 <= val <= 2000。

树型路由器网络中最大耗时的两节点路径。

输入样例 1 

3
1 2 3

输出样例 1

6

2 -> 1 -> 3 耗时最大， 2 + 1 + 3 = 6

输入样例 2 

7
1 1 1 0 0 15 20

输出样例 2

28

15 + 1 + 12 = 28

由于数据量较小，直接对于每个叶节点进行DFS+回溯即可，若要追求高效，可以进行剪枝或直接DP

 1 // we have defined the necessary header files here for this problem.
 2 // If additional header files are needed in your program, please import here.
 3 #include<bits/stdc++.h>
 4 using namespace std;
 5 int node[40000];
 6 bool visits[40000];
 7 int mmax=-1;
 8 void DFS(int *graph,int now,int sum) {
 9     mmax=max(sum+graph[now],mmax);
10     visits[now] = true;
11     if (graph[now*2]>=0 && visits[now*2] == false) { 
12         DFS(graph,now*2,sum+graph[now]);
13     }
14     if (graph[now*2+1]>=0 && visits[now*2+1] == false) {
15         DFS(graph,now*2+1,sum+graph[now]);
16     }
17     if (now != 1 && visits[now/2] == false) {
18         DFS(graph,now/2,sum+graph[now]);
19     }
20     visits[now] = false;
21 }
22 int main()
23 {
24 
25     // please define the C++ input here. For example: int a,b; cin>>a>>b;;
26     
27     // please finish the function body here.
28     
29     // please define the C++ output here. For example:cout<<____<<endl;
30     int n;
31 
32     
33     memset(node,-1,sizeof(node));
34     memset(visits,false,sizeof(visits));
35     cin>>n;
36     for (int i=1;i<=n;++i){
37         cin>>node[i];
38     }
39     for (int i=n/2+1;i<=n;++i){
40         DFS(node,i,0);
41     }
42     cout<<mmax;
43     return 0;
44 }