POJ 2031 Building a Space Station G++ 最小生成树 Kruskal实现 prim未实现
程序员文章站
2022-07-14 22:17:30
...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
//英语 看博友分析 抄博友程序 最小生成树 Kruskal实现 prim未实现
struct nod{
double x;
double y;
double z;
double r;
}da[120];
struct edge{
int a;
int b;
double dis;
};
vector<edge> ve;
bool cmp(edge x, edge y)
{
return x.dis<y.dis;
}
double fun(double x1,double y1, double z1,double x2, double y2,double z2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
}
int fa[120];
int find(int x)
{
if(fa[x]==-1)
{
return x;
}else
{
return fa[x]=find(fa[x]);
}
}
int main()
{
while(1)
{
ve.clear();
memset(fa,-1,sizeof(fa));
int n;
cin>>n;
if(n==0)
{
break;
}
for(int i=0;i<n;i++)
{
cin>>da[i].x>>da[i].y>>da[i].z>>da[i].r;
}
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
double t=fun(da[i].x, da[i].y, da[i].z, da[j].x, da[j].y, da[j].z)-da[i].r-da[j].r;
if(t<0)
{
t=0;
}
ve.push_back((edge){i,j,t});
}
}
sort(ve.begin(),ve.end(),cmp);
double ans=0;
for(int i=0;i<ve.size();i++)
{
int a=ve[i].a;
int b=ve[i].b;
if(find(a)!=find(b))
{
ans=ans+ve[i].dis;
fa[find(a)]=find(b);
}
}
cout<<fixed<<setprecision(3)<<ans<<endl;
}
return 0;
}