[ An Ac a Day ^_^ ][kuangbin带你飞]专题六 最小生成树 POJ 2031 Building a Space Station
2024-08-27 03:43:36
最小生成树模板题
注意最后输出用%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 */
最新文章
- android studio 使用jar包,arr包和怎么使用githup开源项目中的aar包或module
- libevent源码分析:hello-world例子
- 并查集——HDOJ-1232-畅通工程
- UNIX网络编程-基本API介绍(二)
- 毫秒数转换为指定格式日期的js代码
- <;<; 链式重载
- WP8.1 实现Continuation程序(打开文件,保存文件等)
- 十、Struts2结果集
- VMware Workstation中linux(centos)与windows7共享文件夹
- C# 常用的工具类
- Linux下安装LANMP环境
- innerhtml 和value值有什么区别
- ERROR: unable to bind listening socket for address ’127
- SpringBoot2.0 项目异常日志,但不影响运行(待解决)
- 【原创】Linux基础之挂载硬盘
- H5与Native交互之JSBridge技术
- 如何在chrome上打开SSL3.0
- kubernetes namespace
- leetcode个人题解——#33 Search in Rotated Sorted Array
- linux基础命令学习(一)系统的关机、重启以及注销