开发者社区云计算文章正文

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

2016-04-28 1085

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

/*
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");
   }
}