10034 - Freckles 克鲁斯克尔最小生成树！～

/*

10034 - Freckles

克鲁斯克尔最小生成树！～ 

*/

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

struct node{

   double x, y;

};

struct tree{

   int u, v;

   double d;

node nd[105];

int f[105];

tree tt[5010];

bool cmp(tree a, tree b){

   return a.d < b.d;

}

int getFather(int x){

   return x==f[x] ? x : f[x]=getFather(f[x]);

int Union(int a, int b){

   int fa=getFather(a), fb=getFather(b);

   if(fa!=fb){

      f[fa]=fb;

      return 1;

   }

   return 0;

} 

int main(){

   int t;

   cin>>t;

   while(t--){

      int n;

      cin>>n;

      for(int i=1; i<=n; ++i){

         cin>>nd[i].x>>nd[i].y;

         f[i]=i;

      }

      int cnt=0;

      for(int i=1; i<n; ++i)

         for(int j=i+1; j<=n; ++j){

            tt[cnt].u=i;

            tt[cnt].v=j;

            tt[cnt++].d=sqrt((nd[i].x-nd[j].x)*(nd[i].x-nd[j].x) + (nd[i].y-nd[j].y)*(nd[i].y-nd[j].y)); 

         }

      sort(tt, tt+cnt, cmp);

      double sum=0.0;

      for(int i=0; i<cnt; ++i){

         if(Union(tt[i].u, tt[i].v))

            sum+=tt[i].d;

      printf("%.2lf\n", sum);

      if(t) printf("\n");

本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3898428.html，如需转载请自行联系原作者