題目大意：

　　有一些炮臺，如果這個炮臺有衛星接收器，那么任意兩個有衛星接收器的炮臺可以通信，不受距離限制；否者，兩個炮臺之間只能通過對講機通信，這是受距離限制的。要買一種對講機，用在需要的炮臺上，要求所有炮臺兩兩之間可以直接或者間接通信，問要買通信距離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\n" , edge[s-1]) ; 84 85 86 } 87 return 0 ; 88 } View Code

?

轉載于:https://www.cnblogs.com/mengchunchen/p/4578751.html

總結

以上是生活随笔為你收集整理的poj 2349 求MST中第S大的权值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。