티스토리 뷰

문제: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
댓글
댓글쓰기 폼