注意事项:
本题为"树与图的DFS深度优先遍历—树的重心"的近似题,同时涉及到 单链表模拟邻接表存储图 的操作,建议先理解那篇文章。
题目:
给定一棵树,树中包含 n 个结点(编号1~n)和 n−1 条无向边,每条边都有一个权值。
现在请你找到树中的一条最长路径。
换句话说,要找到一条路径,使得使得路径两端的点的距离最远。
注意:路径中可以只包含一个点。
输入格式
第一行包含整数 n。
接下来 n−1 行,每行包含三个整数 ai,bi,ci,表示点 ai 和 bi 之间存在一条权值为 ci 的边。
输出格式
输出一个整数,表示树的最长路径的长度。
数据范围
1≤n≤10000,
1≤ai,bi≤n,
−1e5≤ci≤1e5
输入:
6
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
输出:
22
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010, M = N*2;
int n, ans; //ans存储最终答案
int h[N], e[M], ne[M], w[M], idx = 0; //单链表模拟邻接表
//邻接表增加一条边
void add(int a, int b, int c) {
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
//dfs数位dp,u是当前节点,f是当前节点的上一个节点(父节点)
int dfs(int u, int f) {
int dist = 0; //从当前点往下走的最大长度
int d1 = 0, d2 = 0; //表示挂在当前点上的最长路径d1和次长距离d2
//枚举当前点i能到达的所有子节点j(遍历单链表)
for (int i = h[u]; i!=-1; i=ne[i]) {
int j = e[i];
if (j == f) continue; //由于是无向边,从a到b和从b到a都能走,但我们希望只能向下走,所以不能走回父节点
int d = dfs(j, u) + w[i]; //子节点j往下走的最大长度 + j到i的边权
dist = max(dist, d);
//两种情况: 1.如果d大于等于d1,原本的最长路径就变为了次长路径,再把d存为最长路径 / 2.如果d不大于d1,但大于d2,直接更新即可
if (d >= d1) {d2 = d1, d1 = d;}
else if (d > d2) {d2 = d;}
}
ans = max(ans, d1+d2); //d1+d2得到的就是穿过当前这个点的最长路径,因为一条最长向下的路 + 一条次长向下的路,合起来就是最长的路
return dist;
}
int main() {
//读入
cin >> n;
memset(h, -1, sizeof h); //所有链头都指向-1即可
for (int i = 0; i<n-1; i++) { //n-1条无向边
int a, b, c;
cin >> a >> b >> c;
add(a, b, c); add(b, a, c);
}
dfs(1, -1); //初始父节点随便设个不存在的就行
cout << ans;
return 0;
}
思路:
整体的思路不算难,首先,树可以被"拎起来",也就是可以随意挑一个点为根节点,
剩下的点都向下延申 (大家都见过二叉树吧?长得差不多,只不过可以有多个子节点)。
可以通过dfs来枚举所有路径的"最高"节点,假设当前路径为1-2-3,最高节点是2,
如何找到最高点为2的所有路径中的最长路径?
就是找到所有从节点2往下延申的路径中最长的那条和次长的那条,加起来即为答案,
dfs返回的是当前节点向下延申的最长路径,这样如果有多个子节点,就可以直接比较dfs+w[i,j]的返回结果即可。
还有更新最长和次长路径时会遇到的情况:
1.如果新的路径d大于等于d1,原本的最长路径就变为了次长路径,再把d存为最长路径
2.如果d不大于d1,但大于d2,直接更新即可
如果有所帮助请给个免费的赞吧~有人看才是支撑我写下去的动力!文章来源:https://www.toymoban.com/news/detail-433780.html
声明:
算法思路来源为y总,详细请见https://www.acwing.com/
本文仅用作学习记录和交流文章来源地址https://www.toymoban.com/news/detail-433780.html
到了这里,关于C++---树形DP---树的最长路径(每日一道算法2023.5.4)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!