P8074 SVEMIR
\(Solution\) ：
这道题目乍一看感觉好难...
因为有绿色的加持，再加上一进题目就看见了头疼的三维坐标，不知道的还以为需要用到什么非常高大上的知识来解决这道题，其实只需要用到最小生成树就行了。
不会最小生成树的请出门左转：P3366 【模板】最小生成树
然后来仔细阅读一下这道题，发现题目中给了我们 \(n\) 个节点。
而我们需要计算出使这 \(n\) 个节点连通的最小距离，这道题目的难点就在于你该如何去存边。
如果采用暴力存边，那么边的数量将会到达 \(\frac{n*(n-1)}{2}\) 条边。
然而题目中的数据范围 \(n \le 10^5\) ，这样的话我们就会要存 \(5 \times 10^9\) 条边，这样明显会 \(MLE\) 。
所以我们应该想到该如何去优化存边，找到存边最优的方法。
既然要找到最优的方法，那么必然要减少存边的数量，那么该如何减少呢？
你想想，假如你有一百次抽奖机会，奖项有一等奖，二等奖和谢谢惠顾，那么等你抽完以后，是不是对于那些你抽到的谢谢惠顾，你就不管它们，直接丢掉了？只会留下那些上面写着一等奖，二等奖的卡片。
所以这道题目也是一样，对于那些明显没有贡献，可有可无的边，我们可以直接不去管它，直接跳过它。
所以这道题正确的存边思路是：进行三次排序，每次分别按 \(x\) , \(y\) , \(z\) 从小到大排序。
然后再把每次排序后相邻的两组数之间存一条边.
这样就是完美的保证了题目中要求的 \(min(|x_A-x_B|,|y_A-y_B|,|z_A-z_B|)\) 中每个数据的存在性。
并且这样存边的话最多也只会到 \(300000\) 条边，远远少于前面的 \(5 \times 10^9\) 条边，非常完美地解决了存边这个问题。
好！既然存边这个问题解决了，那么剩下来的也就不攻自破了，你只需要根据我上面说的建立一个图，然后用 \(Kruskal\) 跑一遍最小生成树就可以啦~！
奉上代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
struct node{
int x,y,z;
int bh;
}a[N];
struct Node{
int u,v,w;
}e[N*3];
int n,tot,cnt,ans;
int f[N];
inline int read(){
char c=getchar();int f=1,x=0;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
bool cmp1(Node a,Node b){return a.w<b.w;}
bool cmp2(node a,node b){return a.x<b.x;}
bool cmp3(node a,node b){return a.y<b.y;}
bool cmp4(node a,node b){return a.z<b.z;}
int find(int x){
if(f[x]==x) return x;
else return f[x]=find(f[x]);
}
int join(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy) return 0;
f[fx]=fy; return 1;
}
void add(int u,int v,int w){
tot++;
e[tot].u=u;
e[tot].v=v;
e[tot].w=w;
}
void Kruskal(){
for(int i=1;i<=tot;i++){
if(join(e[i].u,e[i].v)){
cnt++;
ans+=e[i].w;
if(cnt==n-1) return ;
}
}
}
int main(){
n=read();
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=n;i++){
a[i].x=read();
a[i].y=read();
a[i].z=read();
a[i].bh=i;
}
sort(a+1,a+n+1,cmp2);
for(int i=1;i<n;i++) add(a[i].bh,a[i+1].bh,a[i+1].x-a[i].x);
sort(a+1,a+n+1,cmp3);
for(int i=1;i<n;i++) add(a[i].bh,a[i+1].bh,a[i+1].y-a[i].y);
sort(a+1,a+n+1,cmp4);
for(int i=1;i<n;i++) add(a[i].bh,a[i+1].bh,a[i+1].z-a[i].z);
sort(e+1,e+tot+1,cmp1);
Kruskal();
printf("%d\n",ans);
return 0;
}
\((\) 不开 \(O_2\) 是 \(484ms\) ，开 \(O_2\) 是 \(211ms\) 。 \()\)