H

如果我们把所有的点两两之间连边，题目很明显是找到该图的一个最小生成树。

现在我们需要减少边的数量。

首先容易想到当两个点之间的距离为 ,但两个点之间已经有一条简单路径长度为 ，且满足,则这条长度为的边是没有必要的。

考虑把所有点按排序，并在相邻的两点之间连边。

接着对进行同样的操作。

可以证明没有被连到的边不会产生比已有边更优的情况。

时间复杂度

#define int long long
using namespace std;
const int N=1e5+7,M=1e6;
// const int p=998244353;
const double eps=1e-9,pi=acos(-1.0);
int tt;
int n,m,cnt=0,id=1,num=0,len=200000;
int f[N];
struct Ea{
    int x,y,z;
    int id;
}p[N];
int find(int x){
	if(f[x]==x)return x;
	return f[x]=find(f[x]);
}
bool cmp1(Ea a,Ea b){
    return a.x<b.x;
}
bool cmp2(Ea a,Ea b){
    return a.y<b.y;
}
bool cmp3(Ea a,Ea b){
    return a.z<b.z;
}
int dis(Ea a,Ea b){
    return min({abs(a.x-b.x),abs(a.y-b.y),abs(a.z-b.z)});
}
struct E{
    int w,to,from;
}e[N<<2];
bool cmp(E x,E y){
    return x.w<y.w;
}
void solve(){
	scanf("%lld",&n);
    for(int i=1;i<=n;i++){
    	f[i]=i;
        scanf("%lld%lld%lld",&p[i].x,&p[i].y,&p[i].z);
        p[i].id=i;
    }
    sort(p+1,p+1+n,cmp1);
    for(int i=1;i<n;i++){
        e[++cnt]={dis(p[i],p[i+1]),p[i].id,p[i+1].id};
    }
    sort(p+1,p+1+n,cmp2);
    for(int i=1;i<n;i++){
        e[++cnt]={dis(p[i],p[i+1]),p[i].id,p[i+1].id};
    }
    sort(p+1,p+1+n,cmp3);
    for(int i=1;i<n;i++){
        e[++cnt]={dis(p[i],p[i+1]),p[i].id,p[i+1].id};
    }
    sort(e+1,e+1+cnt,cmp);
    int vv=0;
    int ans=0;
    for(int i=1;i<=cnt;i++){
    	int u=e[i].from;int v=e[i].to;
    	if(find(u)==find(v))continue;
    	int w=e[i].w;
    	ans=ans+w;
    	f[find(v)]=find(u);
    	vv++;
    	if(vv==n-1)break;
	}
	printf("%lld\n",ans);
}
signed main(){
 	tt=1;
	while(tt--){
		solve();
	}
	return 0;
}