Kruskal 并查集

一遍过，本题运用的kruskal的思想，通过并查集实现。
获得两个点以及两个点间的距离，然后从集合中找出距离的最小值。加入到图的集合中，当把所有边都遍历完后，由于这个题，图肯定是连通的。所以只要记录加进来的边的长度(也就是两点间的距离就行）。

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
int n;
const int maxn=101;
float res;
struct Point{
    float x,y;
};
struct G{
    int from;
    int to;
    float weight;
    inline bool operator  <(const G &g)const{
        return weight<g.weight;
    }
};
vector<G> graph;
vector<Point> vec;
int father[maxn];
int height[maxn];
void init(int n){
    for(int i=0;i<=n;i++){
        father[i]=i;
        height[i]=0;
    }graph.clear();
    vec.clear();
    res=0;
}
float getdis(Point x,Point y){
    return pow((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y),0.5);
}
int find(int x){
    if(x!=father[x]){
        father[x]=find(father[x]);
    }
    return father[x];
}
void Union(int x,int y,float weight){
    x=find(x);
    y=find(y);
    if(x!=y){
        res+=weight;
        if(height[x]>height[y]){
            father[y]=x;
        }else if(height[x]<height[y]){
            father[x]=y;
        }else{
            father[x]=y;
            height[y]++;
        }
    }
}

int main(){
    while(cin>>n){
        init(n);
        Point p;
        G g;
        for(int i=0;i<n;i++){
            cin>>p.x>>p.y;
            vec.push_back(p);
        }
        for(int i=0;i<vec.size()-1;i++){
            for(int j=i+1;j<vec.size();j++){
                g.from=i;
                g.to=j;
                g.weight=getdis(vec[i],vec[j]);
                graph.push_back(g);
            }
        }
        sort(graph.begin(),graph.end());
        for(int i=0;i<graph.size();i++){
            Union(graph[i].from,graph[i].to,graph[i].weight);
        }
        printf("%.2f\n",res);
    }
    return 0;
}