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

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # define LL long long
 7 using namespace std ;
 8 
 9 const int INF=0x3f3f3f3f;
10 const int MAXN=510;
11 bool vis[MAXN];
12 double lowc[MAXN];
13 int n ;
14 int l ;
15 double cost[MAXN][MAXN] ;
16 double edge[MAXN] ;
17 
18 struct poin
19 {
20     int x ;
21     int y ;
22 }p[MAXN];
23 
24 bool cmp(double x , double y)
25 {
26     return x > y ;
27 }
28 
29 void Prim()//点是0~n-1
30 {
31     l = 0 ;
32     memset(vis,false,sizeof(vis));
33     memset(edge,0,sizeof(edge));
34     vis[0]=true;
35     for(int i=1;i<n;i++)lowc[i]=cost[0][i];
36     for(int i=1;i<n;i++)
37     {
38         double minc=INF;
39         int p=-1;
40         for(int j=0;j<n;j++)
41             if(!vis[j]&&minc>lowc[j])
42             {
43                 minc=lowc[j];
44                 p=j;
45             }
46             if(minc==INF)return ;//原图不连通
47 
48             edge[l] = minc ;
49             l++ ;
50             vis[p]=true;
51             for(int j=0;j<n;j++)
52                 if(!vis[j]&&lowc[j]>cost[p][j])
53                     lowc[j]=cost[p][j];
54     }
55     return ;
56 }
57 
58 int main()
59 {
60 
61   //  freopen("in.txt","r",stdin) ;
62     int T ;
63     scanf("%d" , &T) ;
64     while(T--)
65     {
66         int s ;
67         scanf("%d %d" ,&s , &n) ;
68         int i , j ;
69         for (i = 0 ; i < n ; i++)
70             for (j = 0 ; j < n ; j++)
71                cost[i][j] = INF ;
72         for (i = 0 ; i < n ; i++)
73             scanf("%d %d" , &p[i].x , &p[i].y) ;
74         for (i = 0 ; i < n ; i++)
75             for (j = i+1 ; j < n ; j++)
76             {
77                 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)) ;
78                 cost[i][j] = t ;
79                 cost[j][i] = t ;
80             }
81         Prim() ;
82         sort(edge,edge+l,cmp) ;
83         printf("%.2lf
" , edge[s-1]) ;
84         
85 
86     }
87     return 0 ;
88 }

View Code