Talk is Cheap, Show Me the Code!

0%

树的直径

Posted on In

给定一棵树，求出这棵树的直径，即两个节点距离的最大值。

输入描述:

输入第一行，一个整数n;
接下来n−1行，每行三个整数a,b,c，表示连接节点a和b的边长为c

输出描述:

输出这棵树的直径。

示例1
输入

6
0 1 3
1 5 4
1 2 2
2 3 1
2 4 5

输出

11

说明

csacademy.com/app/graph_editor

tree_radius1.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int n;
const int M = 100010;
struct Node{
    int to, val;
};

vector<Node>edges[M];

int ans = 0, R=-1;
void dfs(int x, int f, int dis){
    if(dis > ans) {ans = dis, R = x;}
    for(int i=0;i<edges[x].size();i++){
        int y = edges[x][i].to;
        if(y==f) continue;
        dfs(y, x, dis + edges[x][i].val);
    }
    return;
}

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n-1;i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    dfs(0, -1, 0);
    dfs(R, -1, 0);
    printf("%d\n", ans);
    return 0;
}
tree_radius2.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int n;
const int M = 100010;
struct Node{
    int to, val;
};

vector<Node>edges[M];

int ans = 0;
int dfs(int x, int f){
    int fir = 0, sec = 0;
    for(int i=0;i<edges[x].size();i++){
        int y = edges[x][i].to;
        if(y==f) continue;
        int t= dfs(y, x) + edges[x][i].val;
        if(t >fir){
            sec = fir;
            fir = t;
        }
        else if(t > sec)
            sec = t;
    }
    ans = max(ans, fir+sec);
    return fir;
}

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n-1;i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    dfs(0, -1);
    printf("%d\n", ans);
    return 0;
}