社区讨论

50pts求助

P8074 [COCI 2009/2010 #7] SVEMIR参与者 2已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mhjslwts
此快照首次捕获于
2025/11/04 07:50
4 个月前
此快照最后确认于
2025/11/04 07:50
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
int mo[10005], f[10005], m, n, len, cnt, ans;
double maxx = -1e9;
struct node {
	int x, y, z;
}a[10005]; 
struct xxxxx {
	int e, w, v;
}b[10000005];
bool cmp(xxxxx x, xxxxx y) {
	return x.v < y.v;
}

int find(int x) {
	if(f[x] == x) return x;
	return find(f[x]);
}
signed main() { 
	for(int i = 0;i < 10005;i ++) {
		f[i] = i;
	}
	cin >> n;
	for(int i = 1;i <= n;i ++) {
		cin >> a[i].x >> a[i].y >> a[i].z;
	}
	for(int i = 1;i <= n / 2;i ++) {
		for(int j = i + 1;j <= n;j ++) {
			b[++ len].v = min(abs(a[i].x - a[j].x), min(abs(a[i].y - a[j].y), abs(a[i].z - a[j].z)));
			b[len].e = i;
			b[len].w = j;
		}
	}
	sort(b + 1, b + len + 1, cmp);
	for(int i = 1;i <= len;i ++) {
		int x = find(b[i].e), y = find(b[i].w);
		if(x != y) {
			ans += b[i].v;
			f[x] = y;
			if(b[i].v > maxx) maxx = b[i].v;
			cnt ++;
			if(cnt == n - 1) {
				break;
			}
		}
	}
	cout << ans;
} 

回复

6 条回复,欢迎继续交流。

正在加载回复...