MST：最小生成树

  • Kruskal:借助并查集

  • 定义边、点结构体，通过点，构造边

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

const int maxn=101;
int father[maxn];
int height[maxn];
void Initial(int n){
  for(int i=0;i<n;i++){
    father[i]=i;  
    height[i]=1;
  }
}

int Find(int x){
  if(x!=father[x]){
    father[x]=Find(father[x]);
  }
  return father[x];
}

void Union(int x,int y){
  int a=Find(x);
  int b=Find(y);
  if(a==b)return;
  else if(height[a]>height[b])father[b]=a;
  else if(height[a]<height[b])father[a]=b;
  else{
    father[b]=a;
    height[a]++;
  }
}

struct Point{
  double x;
  double y;
};
Point q[maxn];

struct Edge{
  int From;
  int To;
  double dis;
  bool operator <(Edge x)const{
    return dis<x.dis;
  }
};

Edge s[maxn*maxn];

double Kruskal(int n,int m){
  double sum=0;
  sort(s,s+m);
  Initial(n);
  for(int i=0;i<m;i++){
    Edge cur=s[i];
    if(Find(cur.From)!=Find(cur.To)){
      sum+=cur.dis;
      Union(cur.From,cur.To);
    }
  }
  return sum;
}

int main(){
  int n,m;
  while(scanf("%d",&n)!=EOF){
    m=n*(n-1)/2;
    for(int i=0;i<n;i++){//输入点
      scanf("%lf%lf",&q[i].x,&q[i].y);
    }
    int u=0;
    for(int i=0;i<n;i++){//构造边
      for(int j=i+1;j<n;j++){
        s[u].From=i;
        s[u].To=j;
        s[u].dis=sqrt((q[i].x-q[j].x)*(q[i].x-q[j].x)+(q[i].y-q[j].y)*(q[i].y-q[j].y));
        u++;
      }
    }
    double sum=Kruskal(n,m);
    printf("%.2lf\n",sum);
  }
  return 0;
}