剑鱼行动
行动
2023-09-27 14:28:29 时间
剑鱼行动
题目
给出N个点的坐标,对它们建立一个最小生成树,代价就是连接它们的路径的长度,现要求总长度最小。
输入
第一行:一个数n,表示有n个点。
第二到n+1行:两个数,表示每一个点的坐标。
输出
总长度,保留两位小数。
输入样例
5
0 0
0 1
1 1
1 0
0.5 0.5
输出样例
2.83
数据范围
N的值在100以内。
坐标值在[-10000,-10000]到[10000,10000]内。
思路
这道题其实就是一道最小生成树。
不过两点之间的距离我们要用勾股定理来求出,而且要保留两位小数,然后基本就可以了。
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct note
{
int x,y;
double l;
}a[10001];
struct zb
{
double x,y;
}b[101];
int n,k,u,f[101];
double answer;
int find(int x)//寻找这个点的根节点
{
if (f[x]==x) return x;
return f[x]=find(f[x]);
}
void connect(int x,int y)//连接这两个点
{
int xx=find(x),yy=find(y);
if (xx<yy) f[xx]=yy;
else f[yy]=xx;
}
bool cmp(note x,note y)
{
return x.l<y.l;
}
int main()
{
scanf("%d",&n);//读入
for (int i=1;i<=n;i++)
{
f[i]=i;//初始化
scanf("%lf%lf",&b[i].x,&b[i].y);//读入坐标
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (i!=j)
{
double l=sqrt(double(b[i].x-b[j].x)*double(b[i].x-b[j].x)+double(b[i].y-b[j].y)*double(b[i].y-b[j].y));
//通过勾股定理求出两点之间的距离
a[++k]=(note){i,j,l};//记录
}
sort(a+1,a+k+1,cmp);//按边的权值从小到大排序
for (int i=1;i<=k;i++)
if (find(a[i].x)!=find(a[i].y))//如果两个点不相连
{
u++;//线数加一
connect(a[i].x,a[i].y);//连接这两个点
answer+=a[i].l;//答案要加边的权值
if (u==n-1) break;//如果所有点已经联通则直接退出
}
printf("%.2lf",answer);//输出(保留两位小数)
return 0;
}
相关文章
- Linux的实用性 VS 行动主义
- 《关于促进大数据发展的行动纲要》提出三大指导意见
- Hadoop Summit 2014:企业拥抱Hadoop在行动
- 看不到行动谁会相信你的改变
- 大数据IMF传奇行动 Spark history-server 配置 !运维人员的强大工具
- 大数据Spark “蘑菇云”行动前传第4课:零基础彻底实战Scala控制结构及Spark源码解析
- 大数据Spark“蘑菇云”行动第56课:在线广告点击黑名单分析和实现
- 大数据Spark “蘑菇云”行动第39课:Spark中的Broadcast和Accumulator机制解密
- 大数据Spark “蘑菇云”行动第40课:Spark编程实战之aggregateByKey、reduceByKey、groupByKey、sortByKey深度解密
- 大数据Spark “蘑菇云”行动第77课:Spark Streaming性能调优思考和实践方法,发现磁盘空间没有了,怎么办
- 行动 -- 如何根据原因进行决策?