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;
}

Download