poj 2031 Building a Space Station MST

   这种n^2的,还是prim好用

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define INF 1E9
using namespace std;
struct node
{
    double x,y,z,r;
};
double d(node a,node b)
{
    double t=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z))-a.r-b.r;
    return t>0?t:0;
}
node place[101];
bool vis[101];
double dis[101];
int main()
{
    int n;
    while(~scanf("%d",&n)&&n)
    {
        memset(vis,0,sizeof(vis));
        memset(dis,127,sizeof(dis));
        int i,j;
        for(i=0;i<n;i++)
          scanf("%lf%lf%lf%lf",&place[i].x,&place[i].y,&place[i].z,&place[i].r);
        double ans=0,Min,t;
        int now=0;
        for(i=0;i<n;i++)
        {
            Min=INF;
            for(j=0;j<n;j++)
            {
                if(dis[j]>=Min||vis[j])continue;
                Min=dis[j];now=j;
            }
            vis[now]=1;
            if(now)ans+=Min;
            for(j=0;j<n;j++)
            {
                if(vis[j])continue;
                dis[j]=min(dis[j],d(place[now],place[j]));
            }

        }
        printf("%.3f\n",ans);
    }
}
时间: 2024-10-28 14:54:52

poj 2031 Building a Space Station MST的相关文章

poj 2031Building a Space Station(几何判断+Kruskal最小生成树)

/* 最小生成树 + 几何判断 Kruskal 球心之间的距离 - 两个球的半径 < 0 则说明是覆盖的!此时的距离按照0计算 */ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int f[105]; struct ball{ double x, y, z, r;

poj 3625 Building Roads

点击打开链接poj 3625 思路:最小生成树+prim分析:         1 由于点有1000,如果要用kruskal的话最少有1000000条边,所以我么选择用prim算法         2 题目中的点的坐标最大值为10^6,那么如果在平方一下的话会超过int,所以在求两个点之间的距离的时候用在前面乘上一个1.0这样就表示的double从而不会超过int了.         3 题目中的说了,要用64位的浮点数,所以选择用long double .输出的时候是"%0.2Lf"

最小生成树【完结】

第一题 hdu 1232 畅通工程 点击打开hdu 1232 思路:模板题 点击查看代码 第二题 hdu 1233 还是畅通工程 点击打开hdu 1233 思路:模板题 点击查看代码 第三题 uva 10034 Freckles 点击打开uva 10034 思路:模板题 点击查看代码 第四题 uva 10397 Connect the Campus 点击打开uva 10397 思路:模板题 点击查看代码 第五题 uva 10369 Arctic Network 点击打开uva 10369 思路:

Java实现Web版RSS阅读器(三)解析在线Rss订阅

上篇博客< Web版RSS阅读器(二)--使用dTree树形加载rss订阅分组列表>已经写到读取rss订阅列表了,今天就说一下,当获取一条在线rss订阅的信息,怎么去解析它,从而获取文章或资讯. 首先说一下rss的版本.很多人都说rss,但是有相当一部分人,都不知道rss居然不只一种格式.我们常用的订阅格式有Rss和Atom 2种格式.Rss有版本从v0.9一直到现在的v2.0,Atom最新的版本则是1.0. DeveloperWorks有一篇文章<使用 RSS 和 Atom 实现新闻联

编程世界经典秘籍:程序员的提问之道

本文节选于编程世界里非常经典的一份文档,该文档首发于 2001 年,已经过多次迭代更新,详细描述了程序员应该如何在网上有礼貌地.合理地向别人提问以及如何解读答案,比如自己先做足功课:搜索.读文档.读代码等.以下中文版节选是由 ryanhanwu 基于原文 3.10 版的最新翻译,全文较长,有兴趣的可跳转查看完整内容. 简介 在黑客的世界里,当你拋出一个技术问题时,最终是否能得到有用的回答,往往取决于你所提问和追问的方式.本指南将教你如何正确的提问以获得你满意的答案. 不只是黑客,现在开放源代码(

澳大利亚计划成立国家航天局

该计划是在澳大利亚阿德莱德举办的第68界国际天文会议上的主题演讲上宣布的.五十年前,澳洲的第一颗卫星在南澳大利亚发射,五十年后,澳大利亚终于有了自己的航天局. 雷锋网(公众号:雷锋网)了解到此前,澳大利亚是经济合作与发展组织国家中唯二的没有航天局的国家(另一个是冰岛).虽然澳洲已有11000人从事价值40亿美元的航天行业,但是如果缺乏政府的支持,澳大利亚在航天上就难有作为.不过,关于何时何处成立,澳大利亚政府还未给出具体信息.相关人士称,具体的细节将会在2018年三月宣布. 虽然澳大利亚还没有航

主要看气质,十大令人叹为观止的数据中心

长期的雾霾天气,让各位看官的眼睛们受了罪.今天我们就来给大家发一组劲爆图片,给大家养养眼. 提到数据中心,可能你会想到的是冰冷的设备.然而,并不是所有的数据中心都是冷冰冰的,今天我们来看下全球十大美的令你惊叹的数据中心. 瑞典Pionen数据中心 瑞典Pionen数据中心有温室.瀑布.德国潜艇引擎和模拟日光,它能承受氢弹的攻击,看起来非常像007系列电影中反派角色的秘密总部. 当然,它还有有个极具东方韵味的名字--牡丹. 微软芝加哥数据中心 微软最大的数据中心,芝加哥数据中心占地面积70万平方英

国际太空对接标准发布

NASA宣布,国际空间站多边协调委员会(International Space Station Multilateral Coordination Board,缩写MCB)批准了一项太空对接标准,为未来的载入宇宙飞船和无人飞船.以及低地球轨道和深空探测任务飞行器,提供一种通用的对接规范. MCB成员包括了NASA.俄罗斯联邦航天局,日本宇宙航空研究开发机构辅助的日本文部科学省,欧洲航天局和加拿大航天局.MCB主席Bill Gerstenmaier表示,他们的目标是创建一个标准的接口,让两种不同的

俄太空实验动物多殒命 科学家待会珍贵资料

[科技讯]5月20日消息,装载45只老鼠和15只蝾螈等小动物的俄罗斯太空舱,完成绕行地球一个月任务后今天返回地表.这项实验目的在测试生物承受长期飞行的状况,结果大部分动物都没能熬过漫长旅程. 除了45只老鼠大部分在任务过程中丧命,八只沙鼠和15只蝾螈也都没能挺过来,科学家说,死因是装备故障或太空生活的压力.然而,这次任务带回一些资料,科学家希望能为载人探测火星任务铺路. 俄罗斯太空任务控制中心(Russian MissionControl)说,Bion-M太空舱在特殊降落伞系统辅助下,平稳降落在