题解

很简单

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+100;
struct node{
    int x,y,z,id;
}Node[N];
struct edge{
    int u,v,w;
};
bool cmp_x(node a,node b){
    return a.x < b.x;
}
bool cmp_y(node a,node b){
    return a.y < b.y;
}
bool cmp_z(node a,node b){
    return a.z < b.z;
}
bool cmp_edge(edge a,edge b){
    return a.w < b.w;
}
int f[N];
int find(int x){
    if(f[x] == x){
        return x;
    }
    return f[x] = find(f[x]);
}
vector <edge> Edge;
int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        int a,b,c;
        cin >> a >> b >> c;
        Node[i] = {a,b,c,i};
        f[i] = i;
    }
    sort(Node+1,Node+1+n,cmp_x);
    for(int i = 1;i < n;i++){
        Edge.push_back({Node[i].id,Node[i+1].id,abs(Node[i].x-Node[i+1].x)});
    }
    sort(Node+1,Node+1+n,cmp_y);
    for(int i = 1;i < n;i++){
        Edge.push_back({Node[i].id,Node[i+1].id,abs(Node[i].y-Node[i+1].y)});
    }
    sort(Node+1,Node+1+n,cmp_z);
    for(int i = 1;i < n;i++){
        Edge.push_back({Node[i].id,Node[i+1].id,abs(Node[i].z-Node[i+1].z)});
    }
    sort(Edge.begin(),Edge.end(),cmp_edge);
    int cnt = 0;
    int idx = 0;
    LL ans = 0;
    while(cnt < n-1){
        int u = Edge[idx].u;
        int v = Edge[idx].v;
        //cout << u << " " << v << " " << Edge[idx].w << endl;
        if(find(u) != find(v)){
            f[find(u)] = find(v);
            cnt++;
            ans += (LL)Edge[idx].w;
        }
        
        idx++;
    }
    cout << ans;


    return 0;
}

编写不易
请点赞
谢谢