20分求助
查看原帖
20分求助
542199
dxt_楼主2024/8/8 11:47

已和这篇讨论进行认真比对(同为20分),奈何才疏学浅,难寻谬误,故以一关注悬赏,求助大佬

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,cnt;
int fa[N];
struct node{
	int v,u,w;
}t[N*10];
struct dot{
	int x1,x2,x3;
}e[N];
void add(int u,int v,int w){
	t[++cnt].u=u;
	t[cnt].v=v;
	t[cnt].w=w;
}
int find(int u){
	if(u==fa[u]) return u;
	else return fa[u]=find(fa[u]);
}
void merge(int a,int b){
	fa[find(a)]=fa[find(b)];
}
bool cmp1(dot a,dot b){
	return a.x1<b.x1;
}
bool cmp2(dot a,dot b){
	return a.x2<b.x2;
}
bool cmp3(dot a,dot b){
	return a.x3<b.x3;
}
bool cmp(node a,node b){
	return a.w<b.w;
}
void krs(){
	int cnts=0;long long ans=0;
	for(int i=1;i<=cnt;++i){
		if(cnts==n-1) break;
		if(find(t[i].u)==find(t[i].v)) continue;
		merge(t[i].u,t[i].v);cnts++;ans+=t[i].w;
	}
	cout<<ans<<endl;
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		fa[i]=i;
		int a,b,c;
		cin>>a>>b>>c;
		e[i].x1=a;
		e[i].x2=b;
		e[i].x3=c;
	}
	sort(e+1,e+1+n,cmp1);
	for(int i=1;i<n;++i) add(i,i+1,e[i+1].x1-e[i].x1);
	sort(e+1,e+1+n,cmp2);
	for(int i=1;i<n;++i) add(i,i+1,e[i+1].x2-e[i].x2);
	sort(e+1,e+1+n,cmp3);
	for(int i=1;i<n;++i) add(i,i+1,e[i+1].x3-e[i].x3);
	sort(t+1,t+1+cnt,cmp);
	krs();
	return 0;
}
2024/8/8 11:47
加载中...