首页 > 代码库 > 蓝桥杯T32(树的直径)

蓝桥杯T32(树的直径)

2024-09-23 03:02:59   215人阅读

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T32

 

题意：中文题诶～

 

思路：显然给出的地图是一颗树，若能求得树的直径 ans，则答案为：ans*(ans+1)/2 + 10*ans；

对于树的直径：若已知根节点root，则 ans 为 root 高度最大的两颗子树高度和，显然我们可以先dfs一遍找到 root 最高的子树并确定离 root 最远的那个节点 v ；

然后再以 v 为根节点，显然 v 只有一颗子树，那么这颗子树的高度即为此树的直径．只需从 v 出发再dfs一遍即可 ；

所以对于求树的直径我们可以先以任意一点为出发点dfs出距离此节点最远的节点v，再从v出发dfs一遍距离v最远的点，此时求出的距离即为直径；

 

代码：

技术分享 
 1 #include <stdio.h>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <string.h>
 5 using namespace std;
 6 
 7 vector<pair<int,int> >tree[100005];
 8 bool vis[100005];
 9 int end_root,Max_len;
10 
11 void dfs(int x,int len){
12     vis[x]=true;
13     if(len>Max_len) Max_len=len,end_root=x;
14     for(int i=0;i<tree[x].size();i++){
15         if(!vis[tree[x][i].first]){
16             dfs(tree[x][i].first,len+tree[x][i].second);
17         }
18     }
19 }
20 
21 int main(void){
22     int n;
23     while(~scanf("%d",&n)){
24         int max_val=0;
25         memset(tree,0,sizeof(tree));
26         for(int i=1;i<n;i++){
27             int a,b,c;
28             scanf("%d %d %d",&a,&b,&c);
29             tree[a].push_back({b,c});
30             tree[b].push_back({a,c});
31         }
32         Max_len=0;
33         memset(vis,0,sizeof(vis));
34         dfs(1,0);
35         memset(vis,0,sizeof(vis));
36         dfs(end_root,0);
37         long long ans=Max_len;
38         printf("%lld\n",ans*(1+ans)/2+10*ans);
39     }
40 }
View Code

 

蓝桥杯T32(树的直径)


联系
我们