题解 | #Freckles#

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;
}