首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。