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를 이용하면 오프라인으로도 해결할 수 있다고 한다.

#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<int, int>>> 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] >= (1 << 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;
}