poj 2349 Arctic Network

  1 #include<iostream>
  2 #include<cmath>
  3 #include<algorithm>
  4 #include<cstdio>
  5 using namespace std;
  6 #define maxn 600
  7 int par[maxn];
  8 int pos;
  9 int n,cnt,m;
 10 double len;
 11 double tt[maxn];//存选取的道路
 12 struct node
 13 {
 14     int x;
 15     int y;
 16     double w;
 17 };
 18 node e[maxn * (maxn - 1) / 2];
 19 int cmp(const node &a , const node &b)
 20 {
 21     return a.w < b.w;
 22 };
 23 struct p
 24 {
 25     int x;
 26     int y;
 27 } po[maxn];
 28 void init()
 29 {
 30     for(int i = 0; i <= n+5; i++)
 31         par[i] = i;
 32     pos = 0;
 33     len = 0.0;
 34     cnt = 0;
 35 }
 36 int Find(int x)
 37 {
 38     int k,j,r;
 39     r = x;
 40     while(par[r] != r)
 41         r = par[r];
 42     k = x;
 43     while(k != r)
 44     {
 45         j = par[k];
 46         par[k] = r;
 47         k = j;
 48     }
 49     return r;
 50 }
 51 int Merge(int x,int y)
 52 {
 53     int a = Find(x);
 54     int b = Find(y);
 55     if(a != b)
 56     {
 57         par[a] = par[b];
 58         return 1;
 59     }
 60     return 0;
 61 }
 62 void input()
 63 {
 64     int u,v;
 65     for(int i = 1; i <= n; i++)
 66         scanf("%d%d",&po[i].x,&po[i].y);
 67 }
 68 
 69 void make()
 70 {
 71     init();
 72     double dist;
 73     for(int i = 1; i < n; i++)
 74     {
 75         for(int j = i + 1; j <= n; j++)
 76         {
 77             dist = (po[i].x - po[j].x) * (po[i].x - po[j].x) + (po[i].y - po[j].y) * (po[i].y - po[j].y);
 78             e[pos].x = i;
 79             e[pos].y = j;
 80             e[pos].w = sqrt(dist);
 81             pos++;
 82         }
 83     }
 84     sort(e,e+pos,cmp);
 85     for(int i = 0; i < pos; i++)
 86     {
 87         if(Merge(e[i].x,e[i].y))
 88         {
 89             tt[cnt] = e[i].w;
 90             cnt++;
 91         }
 92         if(cnt == n - 1)break;
 93     }
 94 }
 95 int main()
 96 {
 97     freopen("input.txt","r",stdin);
 98     int t;
 99     scanf("%d",&t);
100     while(t--)
101     {
102         scanf("%d%d",&m,&n);
103         input();
104         make();
105         printf("%.2lf
",tt[cnt - m]);
106     }
107 
108     return 0;
109 }