首页 > 代码库 > POJ 2031

POJ 2031

最小生成树

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <math.h>using namespace std;const int Maxn=110;struct Pex{	double x,y,z;	double r;};Pex pt[Maxn];int n;double map[Maxn][Maxn];double disp[Maxn];double dist(Pex &x,Pex &y){	double a=x.x-y.x;	double b=x.y-y.y;	double c=x.z-y.z;	double dis=sqrt(a*a+b*b+c*c);	double e=dis-x.r-y.r;	return e>0?e:0;}void solve(){	bool vis[Maxn]; double ans=0;	memset(vis,false,sizeof(vis));	for(int i=1;i<=n;i++)	disp[i]=map[1][i];	vis[1]=true;	for(int i=1;i<=n;i++){		double mint=1e10; int p=-1;		for(int k=1;k<=n;k++){			if(!vis[k]&&mint>disp[k]){				mint=disp[k];				p=k;			}		}		if(p==-1) break;		ans+=mint;		vis[p]=true;		for(int k=1;k<=n;k++){			if(!vis[k]){				disp[k]=min(disp[k],map[p][k]);			}		}	}	printf("%.3lf\n",ans);}int main(){	while(scanf("%d",&n),n){		for(int i=1;i<=n;i++)		for(int j=i;j<=n;j++)		map[i][j]=map[j][i]=0;		for(int i=1;i<=n;i++)		scanf("%lf%lf%lf%lf",&pt[i].x,&pt[i].y,&pt[i].z,&pt[i].r);		for(int i=1;i<=n;i++){			for(int j=i+1;j<=n;j++){				map[i][j]=map[j][i]=dist(pt[i],pt[j]);			}		}		solve();	}	return 0;}

  

POJ 2031