欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 2031 Building a Space Station G++ 最小生成树 Kruskal实现 prim未实现

程序员文章站 2022-07-14 22:17:30
...

POJ 2031 Building a Space Station G++ 最小生成树 Kruskal实现 prim未实现

POJ 2031 Building a Space Station G++ 最小生成树 Kruskal实现 prim未实现

POJ 2031 Building a Space Station G++ 最小生成树 Kruskal实现 prim未实现

#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;
}