UVA 10369 Arctic Network

浏览数：37 / 时间：2015年06月09日

题目来源：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1310

最小生成树问题，Prim算法在这种给出坐标的情况相对Kruskal算法优势还是很大。

 1 /*AC 19ms*/
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<math.h>
 5 #include<string.h>
 6 #include<algorithm>
 7 #define INF 1000000
 8 const int maxn=500+5;
 9 double lowdist[maxn];
10 bool in[maxn];
11 int x[maxn],y[maxn];
12 double dist(int x1,int y1,int x2,int y2)
13 {
14     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
15 }
16 void prim(int n)
17 {
18     lowdist[1]=0;
19     for(int i=2;i<=n;i++){
20         lowdist[i]=dist(x[1],y[1],x[i],y[i]);
21         in[i]=false;
22     }
23     in[1]=true;
24     for(int i=1;i<n;i++){
25         double mindist=INF;
26         int j=1;
27         for(int k=1;k<=n;k++)
28         if(mindist>lowdist[k] && !in[k]){
29             mindist=lowdist[k];
30             j=k;
31         }
32         in[j]=true;
33         for(int k=1;k<=n;k++){
34             double temp=dist(x[j],y[j],x[k],y[k]);
35             if(lowdist[k]>temp && !in[k])
36                 lowdist[k]=temp;
37         }
38     }
39 }
40 int main()
41 {
42     int t,m,n;
43     scanf("%d",&t);
44     while(t--){
45         scanf("%d%d",&m,&n);
46         for(int i=1;i<=n;i++)
47             scanf("%d%d",&x[i],&y[i]);
48         prim(n);
49         std::sort(lowdist+1,lowdist+1+n);
50         printf("%0.2f\n",lowdist[n-m+1]);
51     }
52     return 0;
53 }