티스토리 뷰

알고리즘 관련/BOJ

BOJ)3176 도로 네트워크

JASON 자손9319 2017. 1. 21. 18:10

문제: icpc.me/3176


N개의 도시와 그 도시를 연결하는 N-1개의 도로 네트워크가 있을 때 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력하는 문제이다.


우리는 모든 도시 쌍에는 그 도시를 연결하는 유일한 경로가 있다는데에서 주어진 그래프가 트리임을 유추할 수 있다.


우리는 문제를 해결하기 위하여 LCA를 이용할 것이다.


우리는 LCA를 구할 때 두 도시의 2^i번째 부모를 저장한다. 이 때 우리는 2^i번째 부모를 저장할 뿐만 아니라 


x번째 정점 기준으로 2^i번째 부모까지의 모든 간선중에 최솟값과 최댓값을 같이 저장할 수 있다.


이를 이용하여 쿼리를 처리하면 문제를 해결할 수 있다.


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
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_N 100000
#define INF 2100000000
using namespace std;
int n, k, par[MAX_N + 1][21], qmax[MAX_N + 1][21], qmin[MAX_N + 1][21], d[MAX_N + 1], visited[MAX_N + 1];
vector<vector<pair<intint>>>vt;
void dfs(int here, int depth) {
    visited[here] = true;
    d[here] = depth;
    for (auto there : vt[here]) {
        if (visited[there.first])
            continue;
        dfs(there.first, depth + 1);
        par[there.first][0= here;
        qmin[there.first][0= there.second;
        qmax[there.first][0= there.second;
    }
}
void f() {
    for (int j = 1; j < 21; j++) {
        for (int i = 1; i <= n; i++) {
            par[i][j] = par[par[i][j - 1]][j - 1];
            qmin[i][j] = min(qmin[i][j - 1], qmin[par[i][j - 1]][j - 1]);
            qmax[i][j] = max(qmax[i][j - 1], qmax[par[i][j - 1]][j - 1]);
        }
    }
}
pair<intint> lca(int x, int y) {
    int rmin = INF;
    int rmax = -INF;
    if (d[x] > d[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--) {
        if (d[y] - d[x] >= (<< i)) {
            rmin = min(rmin, qmin[y][i]);
            rmax = max(rmax, qmax[y][i]);
            y = par[y][i];
        }
    }
    if (x == y)
        return{ rmin,rmax };
    for (int i = 20; i >= 0; i--) {
        if (par[x][i] != par[y][i]) {
            rmin = min(rmin, min(qmin[x][i], qmin[y][i]));
            rmax = max(rmax, max(qmax[x][i], qmax[y][i]));
            x = par[x][i];
            y = par[y][i];
        }
    }
    rmin = min(rmin, min(qmin[x][0], qmin[y][0]));
    rmax = max(rmax, max(qmax[x][0], qmax[y][0]));
    return{ rmin,rmax };
}
int main() {
    scanf("%d"&n);
    vt.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        scanf("%d%d%d"&a, &b, &c);
        vt[a].emplace_back(b, c);
        vt[b].emplace_back(a, c);
    }
    dfs(10);
    f();
    scanf("%d"&k);
    while (k--) {
        int a, b;
        scanf("%d%d"&a, &b);    
        pair<intint> r = lca(a, b);
        printf("%d %d\n", r.first, r.second);
    }
    return 0;
}
cs


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

BOJ)1183 약속  (0) 2017.01.22
BOJ)2150 Strongly Connected Component  (0) 2017.01.21
BOJ)3176 도로 네트워크  (0) 2017.01.21
BOJ)11983 Radio Contact  (0) 2017.01.21
BOJ)1766 문제집  (0) 2017.01.20
BOJ)2623 음악프로그램  (3) 2017.01.20
TAG
댓글
댓글쓰기 폼