admin管理员组

文章数量:814269

剑鱼行动 题解

剑鱼行动

题目

给出N个点的坐标,对它们建立一个最小生成树,代价就是连接它们的路径的长度,现要求总长度最小。N的值在100以内,坐标值在[-10000,10000].结果保留二位小数

输入

第一行 n n n 点的个数
接下来 n n n 行, n n n 个点的坐标

输出

最小总长度

样例

inpu

5
0 0
0 1
1 1
1 0
0.5 0.5

output

2.83

解题思路

板子 + 特殊求两点之间的距离 + 保留 2 位小数

代码

#include<iostream>
#include<iomanip>  //保留小数的头文件
#include<cstdio>
#include<cmath>
using namespace std;
int p[120],n;
double f[120][120],m[120],ans;
struct c{double x,y; 
}a[120];
int main()
{memset(m,0x7f,sizeof(m));scanf("%d",&n);for (int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)f[i][j]=sqrt(pow(a[i].x-a[j].x,2)+pow(a[i].y-a[j].y,2));  //两点之间的距离公式m[1]=0.0;for (int i=1;i<=n;i++)  //板子呀{int k=0;for (int j=1;j<=n;j++)if (p[j]==0&&m[j]<m[k])k=j;p[k]=1;ans+=m[k];for (int j=1;j<=n;j++)if (p[j]==0&&m[j]>f[k][j])m[j]=f[k][j];  }cout<<setprecision(2)<<fixed<<ans;  //保留2位小数return 0;
}

本文标签: 剑鱼行动题解