2887번: 행성 터널

https://www.acmicpc.net/problem/2887


$O(nlgn)$

최종적으로 연결된 임의의 두 행성 a,b의 비용으로 선택된 성분을 w라고 하자.( 비용은 |wa-wb| )
그렇다면 두 행성을 제외한 어떠한 행성들도 w성분이 wa, wb 사이값을 가지지 않는 경우가 해집합에 존재한다.
사이값을 가지는 행성 c가 존재할 경우, a-b 연결 대신에 a-c, c-b 연결이 항상 최선이기 때문이다.
따라서 각 성분마다 정렬을 하며, 해당 성분값이 인접한 두 행성마다 간선을 만들어주고 이 간선들을 이용해 mst를 만들면 된다.

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX_N = 1e5;
int n, flag[MAX_N], a[MAX_N][3], c;
long long r;
pair<int, int> p[MAX_N];
int f(int x) {
    if (x == flag[x]) return x;
    return flag[x] = f(flag[x]);
}
struct st {
    int x, y, d;
    bool operator<(st i) const {
        return d < i.d;
    }
}q[MAX_N * 3];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d %d", &a[i][0], &a[i][1], &a[i][2]), flag[i] = i;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < n; j++) p[j] = { a[j][i],j };
        sort(p, p + n);
        for (int j = 0; j < n - 1; j++) q[c++] = { p[j].second,p[j + 1].second,p[j + 1].first - p[j].first };
    }
    sort(q, q + c);
    for (int i = 0; i < c; i++) {
        int ra = f(q[i].x), rb = f(q[i].y);
        if (ra ^ rb) flag[rb] = ra, r += q[i].d;
    }
    printf("%lld", r);
    return 0;
}