티스토리 뷰

알고리즘 관련/BOJ

BOJ)5038 Flight Planning

JASON 자손9319 2017. 7. 9. 14:42

문제: icpc.me/5038


트리가 주어질 때 하나의 간선을 삭제하고 다시 하나의 간선은 연결하여 만든 트리의 지름이 최소가 되도록 하는 문제이다.


N제한이 2500밖에 안되기 때문에 모든 간선을 다 삭제해 본 뒤 지름을 비교해보는걸 생각해볼 수 있다.


그렇다면 하나의 간선을 제거하였을 때 트리의 지름이 최소가 되도록 간선을 이어붙이려면 어떻게 붙여야할까?


바로 트리의 반지름을 이용하면 된다.


트리의 간선을 하나를 제거하면 두개의 트리가 생기게 된다.


이 때 두 트리의 반지름을 각각 구해준 뒤 반지름을 형성하는 정점들 사이에 간선을 연결하면 


트리의 지름은 max(트리1의 지름,트리2의 지름,트리1의 반지름+트리2의 반지름+1)이 된다.


따라서 모든 경우에 대하여 트리의 지름을 구해준 뒤 비교하여 답을 출력해주면 된다.


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
99
100
#include <cstdio>
#include <algorithm>
#include <vector>
#define INF 987654321
using namespace std;
vector<pair<intint>> edge, f;
vector<int> dist, visited, visited2, back, ra;
int n, x, y, r, u, v, rr, idx;
vector<vector<int>> vt;
void dfs(int here, int dis) {
    visited[here] = 1;
    dist[here] = dis;
    if (r <= dist[here]) {
        r = dist[here];
        u = here;
    }
    for (auto next : vt[here]) {
        if (visited[next])continue;
        dfs(next, dis + 1);
    }
}
void dfs2(int here, int dis) {
    visited2[here] = 1;
    dist[here] = dis;
    if (r < dist[here]) {
        r = dist[here];
        v = here;
    }
    for (auto next : vt[here]) {
        if (visited2[next])continue;
        dfs2(next, dis + 1);
        back[next] = here;
    }
}
pair<intint> solve(int e) {
    vt.clear();
    vt.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        if (i == e)continue;
        vt[edge[i].first].push_back(edge[i].second);
        vt[edge[i].second].push_back(edge[i].first);
    }
    dist.assign(n + 1, INF);
    visited.assign(n + 10);
    visited2.assign(n + 10);
    back.assign(n + 10);
    f.clear();
    ra.clear();
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (visited[i])continue;
        r = 0;
        v = i;
        dfs(i, 0);
        r = 0;
        back[u] = 0;
        dfs2(u, 0);
        f.push_back({ v,r });
        res = max(r, res);
    }
    int xx = -1, yy;
    for (int i = 0; i < 2; i++) {
        pair<intint> next = f[i];
        int it = next.first;
        int g = INF;
        while (it) {
            int rad = max(dist[it], next.second - dist[it]);
            if (rad < g) {
                g = rad;
                if (!i)
                    xx = it;
                else
                    yy = it;
            }
            it = back[it];
        }
        ra.push_back(g);
    }
    int sol = max(max(f[0].second, f[1].second), ra[0+ ra[1+ 1);
    if (rr > sol) {
        rr = sol;
        idx = e;
    }
    return{ xx,yy };
}
int main() {
    scanf("%d"&n);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d"&x, &y);
        edge.push_back({ x,y });
    }
    rr = INF;
    for (int i = 0; i < n - 1; i++)
        solve(i);
    printf("%d\n", rr);
    pair<intint> s = solve(idx);
    printf("%d %d\n", edge[idx].first, edge[idx].second);
    printf("%d %d\n", s.first, s.second);
    return 0;
}
cs


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

BOJ)10637 Minimum Spanning Tree  (0) 2017.07.21
BOJ)2261 가장 가까운 두 점  (1) 2017.07.09
BOJ)5038 Flight Planning  (0) 2017.07.09
BOJ)8872 빌라봉  (0) 2017.07.08
BOJ)1444 숌 언어  (0) 2017.07.05
BOJ)9023 연습시즌  (0) 2017.06.22
댓글
댓글쓰기 폼