http://poj.org/problem?id=2031

题意:给出n个球的圆心坐标x,y,z, 半径r,若任意两球不相交,则在两球间建桥。问需建桥的最短距离是多少。

思路:建图,以两球间相差的距离为权值,然后求最小生成树。

 #include <stdio.h>
#include <math.h>
#include <string.h>
const int inf=<<;
const double eps=1e-;
const int maxn=;
double sum,Map[maxn][maxn],dis[maxn];
int vis[maxn];
struct point
{
double x,y,z,r;
};
void prim(int n)
{
for (int i = ; i <= n; i++)
dis[i]=inf;
dis[]=;
sum=;
for (int i = ; i <= n; i++)
{
double Min=inf;
int pos=;
for (int j = ; j <= n; j++)
{
if (!vis[j]&&dis[j] < Min)
{
Min = dis[j];
pos = j;
}
}
if (Min==inf)
return;
vis[pos] = ;
sum+=Min;
for (int j = ; j <= n; j++)
{
if (!vis[j]&&dis[j] > Map[pos][j])
dis[j] = Map[pos][j];
}
}
}
void init()
{
sum = ;
memset(vis,,sizeof(vis));
memset(Map,,sizeof(Map));
}
double dist(point &a,point &b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
}
int main()
{
int n;
while(~scanf("%d",&n)&&n)
{
point a[];
init();
for (int i = ; i <= n; i++)
{
scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z,&a[i].r);
}
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
{
double d = sqrt(dist(a[i],a[j]));
if (d-(a[i].r+a[j].r)>eps)
Map[i][j] = d-a[i].r-a[j].r;
else
Map[i][j] = ;
}
}
prim(n);
printf("%.3f\n",sum);
}
return ;
}

最新文章

  1. css兼容性大坑
  2. Oracle创建主外键
  3. easy UI简单使用介绍
  4. Hibernate 异常 —— No CurrentSessionContext configured
  5. hadoop2.2.0伪分布式搭建
  6. 《JavaScript高级程序设计 第3版》-学习笔记-2
  7. 什么是JPA
  8. Mifare 1卡的存储结构
  9. Dede文章列表
  10. JDBC 基础概念
  11. ThinkPHP中 按条件查询后列表显示
  12. CocoaPods的安装及设置
  13. Data Structure(2)
  14. HDU5804--Price List
  15. jQuery Ajax post多个值传参
  16. 谈Ajax的Get和Post的区别
  17. mybatis什么时候用resulttype 什么时候用resultmap
  18. Android-Chart
  19. Storm入门(六)深入理解可靠性机制
  20. java基本类型的默认值

热门文章

  1. Linux 配置JDK + MyEclipse
  2. Centos 编译安装Haproxy
  3. Shell基本运算符
  4. Redis 之服务器集群配置
  5. 本地运行项目成功 ,但在服务器运行程序就会报Failed to establish a new connection: [Errno -2] Name or service not known
  6. Python 递归、匿名函数、map和filter day4
  7. Whl自助搜索下载器
  8. PHP中的几个随机数生成函数
  9. BUAA_OO_博客作业二
  10. 【 Educational Codeforces Round 51 (Rated for Div. 2) F】The Shortest Statement