首页 > 代码库 > POJ 2031 Building a Space Station(最小生成树)
POJ 2031 Building a Space Station(最小生成树)
题目链接:Building a Space Station
最小生成树的模板题,prim和kuruskal都可以,但是要注意精度损失。
题意:给定一个三维坐标系,给定一些圆的圆心坐标,和半径,求出所有圆心构成的最小生成树;
特别注意:两个圆如果相交在一起,算做联通,距离为0;
C++提交
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define INF 1e7 using namespace std; struct node { double x,y ,z, r; }g[100001]; double ma[101][101]; int n; double SUM(int i,int j) { double ju; ju=sqrt((g[i].x-g[j].x)*(g[i].x-g[j].x)+(g[i].y-g[j].y)*(g[i].y-g[j].y)+(g[i].z-g[j].z)*(g[i].z-g[j].z)); ju = ju - g[i].r - g[j].r; if(ju>=0) return ju; return 0; } double sum; double dis[101],mi; int pos; bool vis[101]; void prim() { sum=0; for(int i=0;i<n;i++) { dis[i]=ma[0][i]; } vis[0]=1; for(int i=0;i<n;i++) { pos = 0,mi=INF; for(int j=0;j<n;j++) { if(!vis[j] && mi>dis[j]) { mi=dis[j]; pos=j; } } if(mi==INF) return; sum +=mi; vis[pos]=1; for(int j=0;j<n;j++) { if(dis[j]>ma[pos][j]) { dis[j]=ma[pos][j]; } } } } int main() { int i,j; while(scanf("%d",&n)&&n) { memset(ma,0,sizeof(ma)); memset(vis,0,sizeof(vis)); for(i=0;i<n;i++) scanf("%lf%lf%lf%lf",&g[i].x,&g[i].y,&g[i].z,&g[i].r); for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(i!=j) { ma[i][j]=SUM(i,j); } } } sum = 0; prim(); printf("%.3lf\n",sum); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。