POJ - 2349 Arctic Network

For each case, output should consist of a single line giving the minimum D required to connect the network. Output should be specified to 2 decimal points.

1
2 4
0 100
0 300
0 600
150 750

212.13

 1 #include 2 #include 3 #include 4 #include
 5 #include 6 
 7 using namespace std;
 8 
 9 int f[505];
10 double dian[505][2];
11 struct node
12 {
13     int u,v;
14     double w;
15     friend bool operator (node x,node y)
16     {
17         return x.wy.w;
18     } 
19 }G[250005];
20 
21 int find(int x)
22 {
23     if(x!=f[x])
24         return find(f[x]);
25     return x;
26 }
27 
28 int main()
29 {
30     int n,m,T,S;
31     cin>>T;
32     while(T--)
33     {
34         scanf("%d%d",&S,&n);
35         memset(G,0,sizeof(G));
36         m=0;
37         for(int i=0;i)
38             f[i]=i;
39         for(int i=0;i)
40             cin>>dian[i][0]>>dian[i][1];
41         for(int i=0;i)
42             for(int j=i+1;j)
43             {
44                 double w1=sqrt((dian[i][0]-dian[j][0])*(dian[i][0]-dian[j][0])+(dian[i][1]-dian[j][1])*(dian[i][1]-dian[j][1]));
45                 G[m].u=i;
46                 G[m].v=j;
47                 G[m++].w=w1;
48             }
49         sort(G,G+m);
50         double ans=0;
51         int s=S-1;
52         for(int i=0;i)
53         {
54             int f1=find(G[i].u);
55             int f2=find(G[i].v);
56             if(f1!=f2)
57             {
58                 f[f2]=f1;
59                 ans=G[i].w;
60                 s++;
61             //    cout
62             }
63             if(s==n-1)
64                 break;
65         }
66         //cout
67         printf("%.2f\n",ans);
68     }
69     
70     return 0;
71 }