Arctic Network POJ - 2349 最小生成树之Kruskal算法

  1 #include <cstdio>
  2 #include <fstream>
  3 #include <algorithm>
  4 #include <cmath>
  5 #include <deque>
  6 #include <vector>
  7 #include <queue>
  8 #include <string>
  9 #include <cstring>
 10 #include <map>
 11 #include <stack>
 12 #include <set>
 13 #include <sstream>
 14 #include <iostream>
 15 #define mod 998244353
 16 #define eps 1e-6
 17 #define ll long long
 18 #define INF 0x3f3f3f3f
 19 using namespace std;
 20 
 21 //u表示起点，v表示终点，cost表示花费
 22 struct node
 23 {
 24     int u,v;
 25     double cost;
 26 };
 27 //排序，从小到大
 28 bool cmp(node a,node b)
 29 {
 30     return a.cost<b.cost;
 31 }
 32 //存放边的信息
 33 vector<node> ve;
 34 
 35 //fa表示当前i的最远祖先
 36 int fa[505];
 37 //初始化fa，开始时自己是自己的祖先
 38 void init(int qwq)
 39 {
 40     for(int i=0;i<=qwq;i++)
 41     {
 42         fa[i]=i;
 43     }
 44 }
 45 //查找最远祖先，同时进行路径压缩
 46 int find(int x)
 47 {
 48     if(fa[x]==x)
 49     {
 50         return x;
 51     }
 52     return fa[x]=find(fa[x]);
 53 }
 54 //判断最远祖先是否相同
 55 bool che(int x,int y)
 56 {
 57     return find(x)==find(y);
 58 }
 59 //合并x,y，把他们放到同一个家族中
 60 void mer(int x,int y)
 61 {
 62     if(!che(x,y)) 
 63     {
 64         fa[fa[x]]=fa[y];
 65     }
 66     return ;
 67 }
 68 int n,m;
 69 struct dian
 70 {
 71     double x,y;
 72 };
 73 dian di[505];
 74 vector<node> aggre;
 75 double dist(dian a,dian b)
 76 {
 77     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
 78 }
 79 int main()
 80 {
 81     scanf("%d",&n);
 82     while(n--)
 83     {
 84         int s,p;
 85         scanf("%d %d",&s,&p);
 86         //初始化
 87         init(p);
 88         for(int i=0;i<p;i++)
 89         {
 90             scanf("%lf %lf",&di[i].x,&di[i].y);
 91         }
 92         node no;
 93         //将站点的位置信息转换成点与点之间的距离并放入到容器中
 94         for(int i=0;i<p-1;i++)
 95         {
 96             for(int j=i+1;j<p;j++)
 97             {
 98                 no.u=i;
 99                 no.v=j;
100                 no.cost=dist(di[i],di[j]);
101                 ve.push_back(no);
102             }
103         }
104         //排序
105         sort(ve.begin(),ve.end(),cmp);
106         //算法求出树的枝条并放入另一个容器中
107         for(int i=0;i<ve.size();i++)
108         {
109             if(!che(ve[i].u,ve[i].v))
110             {
111                 mer(ve[i].u,ve[i].v);
112                 no = ve[i];
113                 aggre.push_back(no);
114             }
115         }
116         //排序
117         sort(aggre.begin(),aggre.end(),cmp);
118         int ans=aggre.size()-1;
119         //从小到大，再减去卫星连接的枝条，
120         if(s-1>0)
121         {
122             ans-=(s-1);
123         }
124         printf("%.2lf\n",aggre[ans].cost);
125         //清除容器的内容
126         ve.clear();
127         aggre.clear();
128     }
129 }