题目：给你n，接下来n行每行四个数，空间坐标x ，y，z和半径，求最小生成树
思路：根据空间坐标半径，求出各个球（可以看成球）重不重叠，重叠就用并查集搞一下，然后数据搞成边的结构体形式，就是道简单最小生成树了
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> //const int maxn = 1e5+5; #define ll long long #define lowbit(x) x&(-x) ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} #define MAX INT_MAX #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl using namespace std; int n,m,tail; double ans; int pre[11000]; struct node { double x,y,z; }edge[11000]; struct hhh { double x,y,z,r; }v[11000]; double cmp(node a,node b) { if(a.z!=b.z) return a.z<b.z; if(a.x!=b.x) return a.x<b.x; return a.y>b.y; } int Find(int x) { if(pre[x]==x) return x; return Find(pre[x]); } double dis(int a,int b) { double temp=(v[a].x-v[b].x)*(v[a].x-v[b].x)+(v[a].y-v[b].y)*(v[a].y-v[b].y)+(v[a].z-v[b].z)*(v[a].z-v[b].z); temp=sqrt(temp); if(temp<=v[a].r+v[b].r) return 0; return temp-v[a].r-v[b].r; } void besame(int x,int y) { int fx=Find(x); int fy=Find(y); if(fx!=fy) pre[fy]=fx; } void clearr() { tail=0; ans=0; FOR(i,1,n) pre[i]=i; } int main() { while(scanf("%d",&n)) { if(n==0) break; clearr(); FOR(i,1,n) cin>>v[i].x>>v[i].y>>v[i].z>>v[i].r; FOR(i,1,n-1) //小号为头 { FOR(j,i+1,n) { if(dis(i,j)==0) besame(i,j); else { edge[++tail].x=i; edge[tail].y=j; edge[tail].z=dis(i,j); } } } sort (edge+1,edge+1+tail,cmp); FOR(i,1,tail) { int fx=Find(edge[i].x); int fy=Find(edge[i].y); if(fx==fy) continue; pre[fy]=fx; ans+=edge[i].z; } cout<<fixed<<setprecision(3)<<ans<<endl; } }