poj 2349 求MST中第S大的权值

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目大意：

有一些炮台，如果这个炮台有卫星接收器，那么任意两个有卫星接收器的炮台可以通信，不受距离限制；否者，两个炮台之间只能通过对讲机通信，这是受距离限制的。要买一种对讲机，用在需要的炮台上，要求所有炮台两两之间可以直接或者间接通信，问要买通信距离D至少为多少的对讲机可以满足要求。

有S个卫星接收器，那么就可以减少S-1个距离开销。要让D尽可能小，就让这S-1个距离开销最大，所以，想法就是，求这些点的最小生成树，然后把所选的边排序，第S大的边的权值就是所求。
假如有4个点，2个卫星，那么最长的那条边可以用卫星，第2长的边就是最小的D，

Sample Input

1 //T
2 4 //卫星数量结点数量
0 100
0 300
0 600
150 750
Sample Output

212.13

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 # include <algorithm>

 # include <cmath>

 # define LL long long

 using namespace std ;

 const int INF=0x3f3f3f3f;

 const int MAXN=;

 bool vis[MAXN];

 double lowc[MAXN];

 int n ;

 int l ;

 double cost[MAXN][MAXN] ;

 double edge[MAXN] ;

 struct poin

 {

     int x ;

     int y ;

 }p[MAXN];

 bool cmp(double x , double y)

 {

     return x > y ;

 }

 void Prim()//点是0~n-1

 {

     l =  ;

     memset(vis,false,sizeof(vis));

     memset(edge,,sizeof(edge));

     vis[]=true;

     for(int i=;i<n;i++)lowc[i]=cost[][i];

     for(int i=;i<n;i++)

     {

         double minc=INF;

         int p=-;

         for(int j=;j<n;j++)

             if(!vis[j]&&minc>lowc[j])

             {

                 minc=lowc[j];

                 p=j;

             }

             if(minc==INF)return ;//原图不连通

             edge[l] = minc ;

             l++ ;

             vis[p]=true;

             for(int j=;j<n;j++)

                 if(!vis[j]&&lowc[j]>cost[p][j])

                     lowc[j]=cost[p][j];

     }

     return ;

 }

 int main()

 {

   //  freopen("in.txt","r",stdin) ;

     int T ;

     scanf("%d" , &T) ;

     while(T--)

     {

         int s ;

         scanf("%d %d" ,&s , &n) ;

         int i , j ;

         for (i =  ; i < n ; i++)

             for (j =  ; j < n ; j++)

                cost[i][j] = INF ;

         for (i =  ; i < n ; i++)

             scanf("%d %d" , &p[i].x , &p[i].y) ;

         for (i =  ; i < n ; i++)

             for (j = i+ ; j < n ; j++)

             {

                 double t = sqrt((double)(p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y)) ;

                 cost[i][j] = t ;

                 cost[j][i] = t ;

             }

         Prim() ;

         sort(edge,edge+l,cmp) ;

         printf("%.2lf\n" , edge[s-]) ;

     }

     return  ;

 }