P8074 [COCI 2009/2010 #7] SVEMIR
题目描述
太空帝国要通过建造隧道来联通它的N NN个星球。
每个星球用三维坐标( x i , y i , z i ) (x_i,y_i,z_i)(xi,yi,zi)来表示，而在两个星球A , B A,BA,B之间建造隧道的价格为min { ∣ x A − x B ∣ , ∣ y A − y B ∣ , ∣ z A − z B ∣ } \min\{|x_A-x_B|,|y_A-y_B|,|z_A-z_B|\}min{∣xA−xB∣,∣yA−yB∣,∣zA−zB∣}。
现要建造N − 1 N-1N−1条隧道使得所有的星球都能直接或间接相连。求完成该任务所需的最小总价。
输入格式
第一行，一个整数N NN。
接下来的N NN行，每行三个整数x i , y i , z i x_i,y_i,z_ixi,yi,zi，表示第i ii个星球的坐标。
数据保证不存在两个具有相同坐标的星球。
输出格式
输出所需的最小总价。
输入输出样例 #1
输入 #1
2 1 5 10 7 8 2输出 #1
3输入输出样例 #2
输入 #2
3 -1 -1 -1 5 5 5 10 10 10输出 #2
11输入输出样例 #3
输入 #3
5 11 -15 -15 14 -5 -15 -1 -1 -5 10 -4 -1 19 -4 19输出 #3
4说明/提示
【数据规模与约定】
- 对于100 % 100\%100%的数据，1 ≤ N ≤ 10 5 1 \le N \le 10^51≤N≤105，− 10 9 ≤ x i , y i , z i ≤ 10 9 -10^9 \le x_i,y_i,z_i \le 10^9−109≤xi,yi,zi≤109。
【提示与说明】
题目译自 COCI 2009-2010 CONTEST #7Task 4 SVEMIR。
本题分值按 COCI 原题设置，满分100 100100。
C++实现
#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintN=100005;structPoint{intx,y,z;}a[N];structEdge{intu,v,w;booloperator<(constEdge&x)const{returnw<x.w;}};vector<Edge>E;intfa[N],id[N];intfind(intu){returnu==fa[u]?u:fa[u]=find(fa[u]);}llkruskal(intn){for(inti=1;i<=n;i++)fa[i]=i;sort(E.begin(),E.end());ll ans=0,cnt=0;for(auto[u,v,w]:E){if(cnt==n-1)break;intx=find(u),y=find(v);if(x==y)continue;fa[x]=y;ans+=w;cnt++;}returnans;}voidadd(intu,intv){intdx=abs(a[u].x-a[v].x),dy=abs(a[u].y-a[v].y),dz=abs(a[u].z-a[v].z);E.push_back({u,v,min({dx,dy,dz})});}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;cin>>n;for(inti=1;i<=n;i++){cin>>a[i].x>>a[i].y>>a[i].z;id[i]=i;}sort(id+1,id+n+1,[](intu,intv){returna[u].x<a[v].x;});for(inti=1;i<n;i++)add(id[i],id[i+1]);sort(id+1,id+n+1,[](intu,intv){returna[u].y<a[v].y;});for(inti=1;i<n;i++)add(id[i],id[i+1]);sort(id+1,id+n+1,[](intu,intv){returna[u].z<a[v].z;});for(inti=1;i<n;i++)add(id[i],id[i+1]);cout<<kruskal(n)<<'\n';return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
