백준알고리즘

트리의 지름

먼지의삶 2019. 10. 9. 19:09

https://www.acmicpc.net/problem/1967

 

1967번: 트리의 지름

파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼

www.acmicpc.net

 

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<iostream>
#include<queue>
#include<vector>
#include<utility>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
class Pair{
public:
    int to, value;
    Pair(int to, int value) {
        this->to = to;
        this->value = value;
    }
    bool operator <(Pair& p) {
        return this->to < p.to;
    }
};
int n,ans;
vector<Pair> tree[10001];
bool d[10001];
 
struct info {
    int from, value, parent;
    info(int from, int value, int parent) {
        this->from = from;
        this->value = value;
        this->parent = parent;
    }
};
 
void bfs(int x) {
    queue<info> q;
    d[x] = true;
    vector<int> v[10001];
    for (int i = 0; i < tree[x].size(); i++) {
        q.push(info( tree[x][i].to, tree[x][i].value, tree[x][i].to));
        d[tree[x][i].to] = true;
    }
    
    while (!q.empty()) {
        int from = q.front().from; int value = q.front().value;
        int parent = q.front().parent;
        q.pop();
        if (tree[from].size() == 1) {
            if (v[parent].size() == 0) v[parent].push_back(value);
            if (v[parent][0] < value)
            {
                v[parent].pop_back();
                v[parent].push_back(value);
            }
            continue;
        }
        for (int i = 0; i < tree[from].size(); i++) {
            if (d[tree[from][i].to] == false) {
                d[tree[from][i].to] = true;
                q.push(info( tree[from][i].to, value + tree[from][i].value,parent ));
            }
        }
    }
 
    vector<int> sum;
    for (int i = 0; i < tree[x].size(); i++) {
        sum.push_back(v[tree[x][i].to][0]);
    }
 
    sort(sum.begin(), sum.end());
    if (ans < sum[sum.size() - 1] + sum[sum.size() - 2])
        ans = sum[sum.size() - 1] + sum[sum.size() - 2];
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    int ending = 0;
    for (int i = 0; i < n-1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        tree[a].push_back(Pair(b,c));
        tree[b].push_back(Pair(a, c));
        if (a > ending) ending = a;
    }
    /*for (int i = 1; i <= ending; i++) {
        sort(tree[i].begin(), tree[i].end());
    }*/
    for (int i = 1; i <= n; i++) {
        if (tree[i].size() > 1) {
            bfs(i);
            memset(d, false, sizeof(d));
        }
    }
    cout << ans << '\n';
    
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
  

트리지름문제

그냥 모든 노드들어가서 최대 노드 길이 하나하나 다해줬는데 사실 그럴필요는없다.