2887 행성 터널

까다로운 문제다. MST를 구하는 문제긴 한데 두 행성을 연결할 때 cost가 min(|Xa-Xb|,|Ya-Yb|,|Za-Zb|)이다.

막무가내로 연결하면 간선이 너무 많아지는 문제가 있다. 따라서 x,y,z에 대해서 정렬하고 정렬된 축에 따라 다음 순서에 오는 행성으로만 간선을 연결한다.

그 다음 크루스칼

아직 저게 왜 돌아가는지 잘 이해가 안가므로 나중에 다시 풀어봐야겠다.

#include <stdio.h>
#pragma warning(disable:4996)
typedef long long ll;
 
struct point {
    int x[4];
};
 
point p[100001], temp[400001];
point q[400001];
 
void _sort(int l, int r, int pp) {
    if (l == r || r - 1 == l) return;
    int mid = (l + r) / 2;
    _sort(l, mid, pp);
    _sort(mid, r, pp);
 
    int cur = 0, l_cur = l, r_cur = mid;
    while (l_cur < mid && r_cur < r) {
        if (p[l_cur].x[pp] < p[r_cur].x[pp]) {
            temp[cur++] = p[l_cur++];
        }
        else
            temp[cur++] = p[r_cur++];
    }
    for (; l_cur < mid; l_cur++) temp[cur++] = p[l_cur];
    for (; r_cur < r; r_cur++) temp[cur++] = p[r_cur];
    for (int i = 0; i < r - l; i++) p[l + i] = temp[i];
}
 
void __sort(int l, int r, int pp) {
    if (l == r || r - 1 == l) return;
    int mid = (l + r) / 2;
    __sort(l, mid, pp);
    __sort(mid, r, pp);
 
    int cur = 0, l_cur = l, r_cur = mid;
    while (l_cur < mid && r_cur < r) {
        if (q[l_cur].x[pp] < q[r_cur].x[pp]) {
            temp[cur++] = q[l_cur++];
        }
        else
            temp[cur++] = q[r_cur++];
    }
    for (; l_cur < mid; l_cur++) temp[cur++] = q[l_cur];
    for (; r_cur < r; r_cur++) temp[cur++] = q[r_cur];
    for (int i = 0; i < r - l; i++) q[l + i] = temp[i];
}
 
int n, d[100001], qi;
 
int f(int x) {
    return x == d[x] ? x : d[x] = f(d[x]);
}
 
bool u(int x, int y){
    x = f(x);
    y = f(y);
    if (x != y) {
        d[y] = x;
        return 1;
    }
    return 0;
}
 
ll max(ll a, ll b) { return a > b ? a : b; }
ll min(ll a, ll b) { return a > b ? b : a; }
 
int getdist(int a, int b) {
    return a > b ? a - b : b - a;
}
 
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < 100001; i++) d[i] = i;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        p[i].x[0] = a;
        p[i].x[1] = b;
        p[i].x[2] = c;
        p[i].x[3] = i;
    }
    ll ans = 0;
    for (int i = 0; i < 3; i++) {
        _sort(0, n, i);
        for (int j = 0; j < n - 1; j++) {
            int dist = getdist(p[j].x[i], p[j + 1].x[i]);
            q[qi].x[0] = dist;
            q[qi].x[1] = p[j].x[3];
            q[qi++].x[2] = p[j + 1].x[3];
        }
    }
    __sort(0, qi, 0);
    for (int i = 0; i < qi; i++) {
        if (f(q[i].x[1]) != f(q[i].x[2])) {
            if (u(q[i].x[1], q[i].x[2]))
                ans += q[i].x[0];
        }
    }
    printf("%lld\n", ans);
    return 0;
}