VNEMPIRE - Đế chế
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100000 + 2;
struct empire {
int x, y, z, id;
int distance(const empire &o) {
return min(abs(x - o.x), min(abs(y - o.y), abs(z - o.z)));
}
} a[N];
bool x_cmp(const empire &a, const empire &b) { return a.x < b.x; }
bool y_cmp(const empire &a, const empire &b) { return a.y < b.y; }
bool z_cmp(const empire &a, const empire &b) { return a.z < b.z; }
struct edge {
int u, v, d;
bool operator < (const edge &o) const { return d < o.d; }
edge() {}
edge(int u, int v, int d): u(u), v(v), d(d) {}
} e[3*N];
int p[N], n;
void initSet(int n) { for(int i = 0; i < n; ++i) p[i] = i; }
int getSet(int u) { return p[u] == u ? u : p[u] = getSet(p[u]); }
void enter() {
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
a[i].id = i;
}
}
void addEdge(int &nEdge) {
for(int i = 1; i < n; ++i)
e[nEdge++] = edge(a[i].id, a[i-1].id, a[i-1].distance(a[i]));
}
void solve() {
int nEdge = 0;
sort(a, a+n, x_cmp); addEdge(nEdge);
sort(a, a+n, y_cmp); addEdge(nEdge);
sort(a, a+n, z_cmp); addEdge(nEdge);
sort(e, e + nEdge); initSet(n);
long long res = 0;
for(int cnt = 0, i = 0; cnt != n-1; ++i)
if(getSet(e[i].u) != getSet(e[i].v))
res += e[i].d, p[p[e[i].u]] = p[e[i].v], ++cnt;
printf("%lld\n", res);
}
int main() {
enter();
solve();
return 0;
}