poj 2349 Arctic Network 最小生成树，求第k大条边

题目抽象出来就是有一些告诉坐标的通信站，还有一些卫星，这些站点需要互相通信，其中拥有卫星的任意两个站可以不用发射器沟通，而所有站点的发射器要都相同，但发射距离越大成本越高。

输入的数据意思：

实例个数

卫星个数   站点个数

每个站点的坐标

输出的意思：

发射器最小是多少，保留两位小数

注意事项：

其中卫星数量少于站点，存边的数组下标从0开始的，还有一个坑坑，输出用的.2f，而喜欢用.2lf的我错了四发才发现….

代码如下：

 #include <stdio.h>
 #include <string.h>
 #include <stdlib.h>
 #include <math.h>
 #include <iostream>
 #include <algorithm>
 #include <climits>
 #include <queue> using namespace std; const int N = ;
 double INF = 0x3f3f3f3f3f3f;
 double cost[N][N],used[N];
 bool visit[N];
 double lowc[N];
 int c;
 bool cmp(double a,double b)
 {
     return a>b;
 }
 void Prim(int n)
 {
     memset(visit,false,sizeof(visit));
     visit[] = true;
     for(int i = ; i < n; i++) lowc[i] = cost[][i];
     for(int i = ; i < n; i++)
     {
         double minc = 1.0*INF;
         int p = -;
         for(int j = ; j < n; j++)
         {
             if(!visit[j] && minc - lowc[j] > 1e-)
             {
                 minc = lowc[j];
                 p = j;
             }
         }
         visit[p] = true;
         used[c++]= minc;
         for(int j = ; j < n; j++)
         {
             if(!visit[j] && lowc[j] - cost[p][j] > 1e-)
                 lowc[j] = cost[p][j];
         }
     }
 }
 struct nodes
 {
     double x,y;
 }point[N]; int main(void)
 {
     int i,j,t,m,n;
     scanf("%d",&t);
     while(t--)
     {
         scanf("%d %d",&m,&n);
         for(i = ; i < n; i++)
             scanf("%lf %lf",&point[i].x,&point[i].y);
         for(i = ; i  < n; i++)
             for(j = ; j < n; j++)
                 cost[i][j] = cost[j][i] = INF;         for(i = ; i < n; i++)
             for(j = i + ; j <n; j++)
         {
             double temp = sqrt( (point[i].x-point[j].x)*(point[i].x-point[j].x) +(point[i].y-point[j].y)*(point[i].y-point[j].y));
            cost[i][j] = cost[j][i] = temp;
         }
         memset(used,,sizeof(used));
         c = ;
         Prim(n);
         sort(used,used+c,cmp);
         printf("%.2f\n",used[m-]);//.2f神坑
     }
     return ;
 }