最小生成树模板题

注意最后输出用%f

(从C99开始%f已经不能用于输出double 即 输入用%lf 输出用%f)

 #include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#define M(a,b) memset(a,b,sizeof(a))
#define debug(x) cerr<<#x<<"=="<<(x)<<endl
using namespace std;
typedef long long ll; const int maxn=; int f[maxn],tol,n; struct _edge
{
int u,v;
double w;
}edge[maxn*maxn*maxn]; bool cmp(_edge a,_edge b)
{
return a.w<b.w;
} struct point
{
int a;
double x,y,z,r;
} pt[maxn]; void addedge(point a,point b)
{
edge[tol].u=a.a;
edge[tol].v=b.a;
double len=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;
edge[tol].w=len<?:len;
tol++;
} //void addedge(int u,int v,int w)
//{
// edge[tol].u=u;
// edge[tol].v=v;
// edge[tol].w=w;
// tol++;
//} int _find(int x)
{
if(f[x]==-) return x;
else return f[x]=_find(f[x]);
} double kruskal()
{
M(f,-);
sort(edge,edge+tol,cmp);
int cnt=;
double ans=,w;
int u,v,f1,f2;
for(int i=; i<tol; i++)
{
u=edge[i].u;
v=edge[i].v;
w=edge[i].w;
f1=_find(u);
f2=_find(v);
if(f1!=f2)
{
ans+=w;
f[f1]=f2;
cnt++;
}
if(cnt==n-) break;
}
return ans;
} int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
tol=;
double x,y,z,r;
for(int i=; i<n; i++)
{
pt[i].a=i;
scanf("%lf%lf%lf%lf",&pt[i].x,&pt[i].y,&pt[i].z,&pt[i].r);
for(int j=; j<i; j++)
{
addedge(pt[j],pt[i]);
}
} printf("%.3f\n",kruskal()); //注意要用%f
}
return ;
}
/* 3
10.000 10.000 50.000 10.000
40.000 10.000 50.000 10.000
40.000 40.000 50.000 10.000
2
30.000 30.000 30.000 20.000
40.000 40.000 40.000 20.000
5
5.729 15.143 3.996 25.837
6.013 14.372 4.818 10.671
80.115 63.292 84.477 15.120
64.095 80.924 70.029 14.881
39.472 85.116 71.369 5.553
0 */

最新文章

  1. android studio 使用jar包,arr包和怎么使用githup开源项目中的aar包或module
  2. libevent源码分析:hello-world例子
  3. 并查集——HDOJ-1232-畅通工程
  4. UNIX网络编程-基本API介绍(二)
  5. 毫秒数转换为指定格式日期的js代码
  6. &lt;&lt; 链式重载
  7. WP8.1 实现Continuation程序(打开文件,保存文件等)
  8. 十、Struts2结果集
  9. VMware Workstation中linux(centos)与windows7共享文件夹
  10. C# 常用的工具类
  11. Linux下安装LANMP环境
  12. innerhtml 和value值有什么区别
  13. ERROR: unable to bind listening socket for address ’127
  14. SpringBoot2.0 项目异常日志,但不影响运行(待解决)
  15. 【原创】Linux基础之挂载硬盘
  16. H5与Native交互之JSBridge技术
  17. 如何在chrome上打开SSL3.0
  18. kubernetes namespace
  19. leetcode个人题解——#33 Search in Rotated Sorted Array
  20. linux基础命令学习(一)系统的关机、重启以及注销

热门文章

  1. maven 启蒙
  2. 如何让Fortran生成不同的随机数
  3. Blend4开发:会飞的小鸟
  4. SZU:B47 Big Integer I
  5. 朴素贝页斯分类法 c++实现
  6. [Usaco2008 Open]Roads Around The Farm分岔路口[水题]
  7. c# 发送Email的2中方式
  8. SVN merge
  9. ruby gsub gsub! chomp chomp! 以及所有类似函数用法及区别
  10. 软件快速开发平台 WebBuilder 6.8