# 题解 | #Freckles#

Freckles

https://www.nowcoder.com/practice/41b14b4cd0e5448fb071743e504063cf

Kruskal算法，并查集，最小生成树

```#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=100;

int father[N]; //父结点
int height[N]; //高度
struct Node{
int value; //给每个结点的值，i从0到n-1
double x; //结点坐标
double y;
};
Node node[N];
struct Edge{
int from;
int to;
double length; //两个结点之间的距离
};
vector<Edge> edge;
bool Compare(const Edge& a,const Edge& b){
return a.length<b.length;
}
//初始化
void init(int n){
for(int i=0;i<n;i++){
father[i]=i;
height[i]=0;
}
edge.clear();
}
//查找根结点
int Find(int x){
if(x!=father[x]){
father[x]=Find(father[x]);
}
return father[x];
}
void Union(int a,int b){
int x=Find(a);
int y=Find(b);
if(x!=y){
if(height[x]>height[y]){
father[y]=x;
}
else if(height[x]<height[y]){
father[x]=y;
}
else{
father[y]=x;
height[x]++;
}
}
}
//判断两个结点是否在一个连通分量中
bool judge(int a,int b){
if(Find(a)==Find(b)) return true;
else return false;
}
void appendedge(Node a,Node b){
Edge temp;
temp.from=a.value;
temp.to=b.value;
double x1,x2,y1,y2;
x1=a.x;
x2=b.x;
y1=a.y;
y2=b.y;
double result=sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
temp.length=result;
edge.push_back(temp);
}
double Kruskal(int n){
double result;
//按照距离排序
sort(edge.begin(),edge.end(),Compare);
for(int i=0;i<edge.size();i++){
if(judge(edge[i].from,edge[i].to)){
continue;
}
Union(edge[i].from, edge[i].to);
result+=edge[i].length;
}
return result;
}
int main() {
int n;
while(cin>>n){
init(n);
for(int i=0;i<n;i++){
node[i].value=i;
cin>>node[i].x>>node[i].y;
}
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
appendedge(node[i],node[j]);
}
}
//kruskal
double totallength=Kruskal(n);
printf("%.2f\n",totallength);
}
return 0;
}
```

1 收藏 评论