#include"bits/stdc++.h"
using namespace std;
#define xx long long
xx r(){
xx x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct nd{xx x,y,z,uid;}a[100001];
struct eg{xx k,l,len;}b[300001];
int n=r(),m,g[100001],ii,Ans;
bool c1(nd a,nd b){return a.x<b.x;}
bool c2(nd a,nd b){return a.y<b.y;}
bool c3(nd a,nd b){return a.z<b.z;}
bool c4(eg a,eg b){return a.len<b.len;}
xx leng(nd a,nd b){return min(min(abs(a.x-b.x),abs(a.y-b.y)),abs(a.z-b.z));}
xx geng(int x){return(g[x]==x)?(x):(geng(g[x]));}
main()
{
	xx i,wx,wy;;eg L;
	for(i=1;i<=n;++i){
		a[i].x=r(),a[i].y=r(),a[i].z=r(),a[i].uid=i;g[i]=i;
	}sort(a+1,a+n+1,c1);for(xx i=1;i<n;++i)b[++m]=(eg){
		a[i].uid,a[i+1].uid,leng(a[i],a[1+i])
	};sort(a+1,a+n+1,c2);for(xx i=1;i<n;++i)b[++m]=(eg){
		a[i].uid,a[i+1].uid,leng(a[i],a[1+i])
	};sort(a+1,a+n+1,c3);for(xx i=1;i<n;++i)b[++m]=(eg){
		a[i].uid,a[i+1].uid,leng(a[i],a[1+i])
	};sort(b+1,b+m+1,c4);
	ii=1;
	for(i=1;i<n;++ii){
		L=b[ii];wx=geng(L.k),wy=geng(L.l);
		if(wx!=wy){
			g[wx]=wy;
			++i;Ans+=L.len;
		}
	}
	cout<<Ans;
}

为什么???求助!

1 条评论

  • 1

信息

ID
350
时间
1000ms
内存
256MiB
难度
6
标签
(无)
递交数
41
已通过
14
上传者