[图论]剑鱼行动:kruskal

剑鱼行动

目录

• 剑鱼行动
• 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;
}