본문 바로가기

알고리즘 관련/BOJ

BOJ)1396 크루스칼의 공

문제: icpc.me/1396


lca를 이용하는 난이도 있는 문제다. 풀이 방법이 재밌다.


x정점에서 y정점으로 이동할 때의 최소온도는 도로네트워크 등의 문제에서 했듯이 두 정점 사이의 lca를 구해나가면서 해당 간선의 가중치의 최댓값도 parent 배열과 같이 저장하는 방법으로 구해낼 수 있으나 공이 움직일 수 있는 범위를 출력하는게 문제가 되었다.


오래 생각해도 모르겠어서 찾아보니까 재밌는 방법으로 이걸 해결할 수 있었다.


MST를 구성하는 과정에서 두 정점을 연결하는 대신 새로운 정점을 생성하는 방법이다.


즉 기존의 정점들은 새로운 그래프에서의 leaf가 되며 n-1개의 정점을 새로 구축하는 방법이다.



예제의 그래프를 새로 구축하면 이런 모양이 될 것이다. (기존의 정점(1~5))


여기서 새로 생기는 정점들은 size와 가중치를 가지게 된다고 해보자.


새로운 정점의 size는 나의 두 자식의 size의 합이며 가중치는 해당 정점을 연결하게 된 기존 그래프의 간선의 가중치다.


이렇게 구축하면 MST에서 크루스칼을 돌릴 때 작은 간선부터 보게되기 때문에 새로운 정점의 가중치는 기존 가중치보다 클 수밖에 없다. 즉 그 구간의 최댓값이 된다고 볼 수 있다.


따라서 이렇게 새로운 그래프를 구축 한 뒤 쿼리를 받으면서 두 정점의 lca를 구해낸 뒤 해당 lca의 size와 가중치를 출력하면 된다.


parallel binary search를 이용하면 오프라인으로도 해결할 수 있다고 한다.


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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, p[200010], par[200010][22], sz[200020], g[200020], h[200020], q;
vector<pair<int, pair<intint>>> edge;
vector<vector<int>> vt;
int find(int h) {
    return h == p[h] ? h : p[h] = find(p[h]);
}
void merge(int x, int y) {
    if (find(x) == find(y))return;
    p[find(y)] = find(x);
}
void dfs(int curr,int prev) {
    for (auto next : vt[curr]) {
        if (next == prev)continue;
        par[next][0= curr;
        h[next] = h[curr] + 1;
        dfs(next, curr);
    }
}
int getlca(int x, int y) {
    if (h[x] > h[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--) {
        if (h[y] - h[x] >= (<< i))
            y = par[y][i];
    }
    if (x == y)return x;
    for (int i = 20; i >= 0; i--) {
        if (par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }
    return par[x][0];
}
int main() {
    scanf("%d%d"&n, &m);
    for (int i = 1; i <= n + m; i++) {
        p[i] = i;
        sz[i] = 1;
    }
    vt.resize(n + m + 1);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        scanf("%d%d%d"&x, &y, &z);
        edge.push_back({ z,{x,y} });
    }
    sort(edge.begin(), edge.end());
    for (int i = n + 1; i <= n + m; i++) {
        int x = edge[i - n - 1].second.first;
        int y = edge[i - n - 1].second.second;
        int z = edge[i - n - 1].first;
        if (find(x) == find(y))continue;
        sz[i] = sz[find(x)] + sz[find(y)];
        g[i] = z;
        vt[i].push_back(find(x));
        vt[i].push_back(find(y));
        merge(i, x);
        merge(i, y);
    }
    for (int i = n + m; i > 0; i--) {
        if (!h[i])
            dfs(i, 0);
    }
    for (int j = 1; j <= 20; j++) {
        for (int i = 1; i <= n + m; i++)
            par[i][j] = par[par[i][j - 1]][j - 1];
    }
    scanf("%d"&q);
    while (q--) {
        int x, y;
        scanf("%d%d"&x, &y);
        if (find(x) != find(y)) {
            puts("-1");
            continue;
        }
        int lca = getlca(x, y);
        printf("%d %d\n", g[lca], sz[lca]);
    }
    return 0;
}
cs


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

BOJ)8217 유성  (1) 2017.06.14
BOJ)14434 놀이기구1  (0) 2017.06.14
BOJ)10319 좀비 아포칼립스  (0) 2017.06.12
BOJ)5651 완전 중요한 간선  (0) 2017.06.12
BOJ)1626 두 번째로 작은 스패닝 트리  (5) 2017.06.12