剑鱼行动【图论】

剑鱼行动

Time Limit:10000MS Memory Limit:65536K
Total Submit:151 Accepted:118
Case Time Limit:1000MS

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

Input
5 ---------------5个点
0 0 ---------------5个点点的坐标
0 1
1 1
1 0
0.5 0.5

Output
2.83

解题思路

这题也是比较纯粹的 模板题，只是要用double。通过预处理求出 两点间距离距离 就可以了。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
using namespace std;
int n,v[200],k;
double f[200][200],ans,minn[200],a[200][3];
int main(){scanf("%d",&n);for(int i=1;i<=n;i++)cin>>a[i][1]>>a[i][2];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=sqrt(pow(a[i][1]-a[j][1],2)+pow(a[i][2]-a[j][2],2));memset(minn,0X7f,sizeof(minn));minn[1]=0.0;for(int i=1;i<=n;i++){k=0;for(int j=1;j<=n;j++)if(!v[j]&&minn[j]<minn[k])k=j;v[k]=1;for(int j=1;j<=n;j++)if(!v[j]&&f[k][j]<minn[j])minn[j]=f[k][j];}for(int i=1;i<=n;i++)ans+=minn[i];cout<<fixed<<setprecision(2)<<ans;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！