工作总结加强部门网站建设,新网互联 网站上传,东莞昨天发生的重大新闻,珠海网站设计费用目录 1 基础知识2 模板3 工程化 1 基础知识
暂无。。。
2 模板
暂无。。。
3 工程化
题目1#xff1a;树的最长路径。
解题思路#xff1a;遍历从根结点到叶子结点的最长距离和次长距离#xff0c;注意遍历每一个下一步#xff0c;因此避免了这两个路径有重叠。更新r… 目录 1 基础知识2 模板3 工程化 1 基础知识
暂无。。。
2 模板
暂无。。。
3 工程化
题目1树的最长路径。
解题思路遍历从根结点到叶子结点的最长距离和次长距离注意遍历每一个下一步因此避免了这两个路径有重叠。更新res即res max(res, d1 d2)。返回最长距离d1。
C代码如下
#include iostream
#include vector
#include unordered_mapusing namespace std;int n;
unordered_mapint, vectorpairint,int g;int res 0;int dfs(int a, int fa) {int d1 0;//d1表示最大长度int d2 0;//d2表示次大长度for (auto [b,c] : g[a]) {if (b fa) continue;int d dfs(b, a) c;if (d d1) {d2 d1;d1 d;} else if(d d2) {d2 d;}}res max(res, d1 d2);return d1;
}int main() {cin n;for (int i 0; i n - 1; i) {int a, b, c;cin a b c;g[a].emplace_back(b,c);g[b].emplace_back(a,c);}dfs(1, -1);cout res endl;return 0;
}题目2树的中心。
解题思路暴力解法遍历每一个结点以该结点为根结点计算到叶子结点的最长路径。
C代码如下
#include iostream
#include vector
#include unordered_mapusing namespace std;int n;
unordered_mapint,vectorpairint,int g;int dfs(int a, int fa) {int d 0;for (auto [b, c] : g[a]) {if (b fa) continue;d max(d, dfs(b, a) c);}return d;
}int main() {cin n;for (int i 0; i n - 1; i) {int a, b, c;cin a b c;g[a].emplace_back(b,c);g[b].emplace_back(a,c);}int res 0x3f3f3f3f;for (int i 1; i n; i) {res min(res, dfs(i, -1));}cout res endl;return 0;
}
