본문 바로가기

알고리즘 관련/BOJ

BOJ)3176 도로 네트워크

문제: 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

태그