首页 > 代码库 > POJ 2031 Building a Space Station
POJ 2031 Building a Space Station
最小生成树问题。
空间坐标系,还有点的半径。
如果两个点距离减去它们的半径小于0,表明他们重叠了。直接并查集合并。
剩下的就排序,并查。
#include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<queue> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 using namespace std; int n,m; struct lx { int u,v; double len; } l[50*101]; int fa[101]; struct node { double x,y,z,r; }point[101]; bool cmp(const lx &a,const lx &b) { return a.len<b.len; } int father(int x) { if(x!=fa[x]) return fa[x]=father(fa[x]); } double getlen(node a,node b) { double len=sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2)+pow(a.z-b.z,2)); return len-a.r-b.r; } int main() { while(scanf("%d",&n),n) { for(int i=1;i<=n;i++) { fa[i]=i; scanf("%lf%lf%lf%lf",&point[i].x,&point[i].y,&point[i].z,&point[i].r); } int cot=0; for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { double len=getlen(point[i],point[j]); if(len<=0) { int fi=father(i); int fj=father(j); if(fi==fj)continue; fa[fj]=fi; } else { l[cot].u=i,l[cot].v=j; l[cot++].len=len; } } } sort(l,l+cot,cmp); double ans=0; for(int i=0;i<cot;i++) { int fu=father(l[i].u); int fv=father(l[i].v); if(fu==fv)continue; fa[fv]=fu; ans+=l[i].len; } printf("%.3f\n",ans); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。