剑鱼行动

目录

• 剑鱼行动
• • Description
  • Input
  • Output
  • Sample Input
  • Sample Output
  • 解析
  • 难点
  • 代码

Description

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

Input

N个点 ,N个点的坐标

Output

连接它们的最短路径的长度

Sample Input

5 —————5个点
0 0 —————5个点点的坐标
0 1
1 1
1 0
0.5 0.5

Sample Output

2.83

解析

这道题一看就是最小生成树，有两种方法，分别为
普里姆算法（prim）
和
克鲁斯卡尔（kruskal）
本题解使用的是 kruskal
假设连通网G＝（V，E），则令最小生成树的初始状态为只有n个顶点而无边的非连通网，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点都在同一连通分量上为止。

难点

题目给出的可能是小数，所以就有了我们的读入方式
aj[i][1]储存x坐标,a[j][2]储存y坐标

for(int i=1;i<=n;i++)scanf("%lf%lf",&aj[i][1],&aj[i][2]);

以及我们的计算距离公式，原理是勾股定理

sqrt((abs(aj[i][1]-aj[j][1]))*(abs(aj[i][1]-aj[j][1]))+(abs(aj[i][2]-aj[j][2]))*(abs(aj[i][2]-aj[j][2])));

代码

模板解析

#include<cmath>
#include<stdio.h>
#include<iostream>
using namespace std;
int n,v[10005],p,q;
double ans,minn,aj[10005][3],a[10005][10005];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lf%lf",&aj[i][1],&aj[i][2]); //神奇的读入~
for(int i=1;i<=n;i++){ //神奇的处理~~~
for(int j=1;j<n;j++){
a[i][j]=sqrt((abs(aj[i][1]-aj[j][1]))*(abs(aj[i][1]-aj[j][1]))+(abs(aj[i][2]-aj[j][2]))*(abs(aj[i][2]-aj[j][2])));
a[j][i]=a[i][j];
}
v[i]=i; //从在开始，都是套模板
}
for(int i=1;i<=n-1;i++){
minn=99999999;
for(int k=1;k<=n;k++)
 for(int j=1;j<=n;j++)
  if(v[k]!=v[j] and a[k][j]<=minn and a[k][j]!=0){
  minn=a[k][j];
  p=j;
  q=k;
  }
ans+=minn;
int ooxx=v[p];
for(int k=1;k<=n;k++){
if(v[k]==ooxx)v[k]=v[q];
}
}
printf("%.2lf",ans); //记得保留两位小数
return 0;
}