본문 바로가기

알고리즘 관련/BOJ

BOJ)14657 준오는 최종인재야!!

문제:icpc.me/14657


문제를 해석해보자면 최대한 많이 문제를 푸는건 결국 주어진 트리를 가중치 없는 그래프에서의 지름에 해당 되는 정점들을 선택하는 경우이다.


하지만 같은 크기를 가지는 지름이 많을 수 있기 때문에 모든 지름을 탐색해야한다.


이를 위하여 지름의 중심이 되는 점을 찾은 뒤 그 점부터 이동 가능한 가장 먼 leaf로의 최단거리를 탐색한 다음 계산해준다.



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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 1e9
using namespace std;
int n, t, a, b, c, r, u, v, res, xx, yy;
vector<vector<pair<intint>>> vt;
vector<int> dist, pv, xxx, yyy;
vector<pair<intint>> ans;
void dfs(int here, int dis) {
    dist[here] = dis;
    if (dist[here] > r) {
        r = dist[here];
        u = here;
    }
    for (auto next : vt[here]) {
        if (dist[next.first] != INF)continue;
        dfs(next.first, dis + 1);
    }
}
void track(int here, int prv) {
    pv[here] = prv;
    for (auto next : vt[here]) {
        if (next.first == prv)continue;
        track(next.first, here);
    }
}
void dfs2(int here, int prv, int dis, int dph) {
    int f = 0;
    for (auto next : vt[here]) {
        if (next.first == prv)continue;
        f = 1;
        dfs2(next.first, here, dis + next.second, dph + 1);
    }
    if (!f) {
        if (dph == r / 2)
            yy = min(yy, dis);
        else if (dph == r / + 1)
            xx = min(xx, dis);
    }
}
int main() {
    scanf("%d%d"&n, &t);
    vt.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d%d"&a, &b, &c);
        vt[a].push_back({ b,c });
        vt[b].push_back({ a,c });
    }
    dist.assign(n + 1, INF);
    dfs(10);
    v = u, r = 0;
    dist.assign(n + 1, INF);
    dfs(u, 0);
    pv.assign(n + 10);
    track(u, 0);
    int it = r / 2;
    while (it--)
        v = pv[v];
    it = v;
    for (auto next : vt[v]) {
        xx = 1e9;
        yy = 1e9;
        dfs2(next.first, v, next.second, 1);
        if (xx != 1e9)
            xxx.push_back(xx);
        else
            yyy.push_back(yy);
    }
    sort(xxx.begin(), xxx.end());
    sort(yyy.begin(), yyy.end());
    if (r % 2) {
        if (r == 1)
            res = xxx[0];
        else
            res = xxx[0+ yyy[0];
    }
    else
        res = yyy[0+ yyy[1];
    printf("%d\n", res / t + (res%t ? 0));
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1999 최대최소  (0) 2017.07.31
BOJ)13511 트리와 쿼리2  (0) 2017.07.31
BOJ)14657 준오는 최종인재야!!  (0) 2017.07.29
BOJ)2300 기지국  (0) 2017.07.25
BOJ)11985 오렌지 출하  (0) 2017.07.24
BOJ)10637 Minimum Spanning Tree  (0) 2017.07.21