题目抽象出来就是有一些告诉坐标的通信站，还有一些卫星，这些站点需要互相通信，其中拥有卫星的任意两个站可以不用发射器沟通，而所有站点的发射器要都相同，但发射距离越大成本越高。
输入的数据意思：
实例个数
卫星个数 站点个数
每个站点的坐标
输出的意思：
发射器最小是多少，保留两位小数
注意事项：
其中卫星数量少于站点，存边的数组下标从0开始的，还有一个坑坑，输出用的.2f，而喜欢用.2lf的我错了四发才发现....
代码如下：
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <iostream> 6 #include <algorithm> 7 #include <climits> 8 #include <queue> 9 10 using namespace std; 11 12 const int N = 505; 13 double INF = 0x3f3f3f3f3f3f; 14 double cost[N][N],used[N]; 15 bool visit[N]; 16 double lowc[N]; 17 int c; 18 bool cmp(double a,double b) 19 { 20 return a>b; 21 } 22 void Prim(int n) 23 { 24 memset(visit,false,sizeof(visit)); 25 visit[0] = true; 26 for(int i = 1; i < n; i++) lowc[i] = cost[0][i]; 27 for(int i = 1; i < n; i++) 28 { 29 double minc = 1.0*INF; 30 int p = -1; 31 for(int j = 0; j < n; j++) 32 { 33 if(!visit[j] && minc - lowc[j] > 1e-8) 34 { 35 minc = lowc[j]; 36 p = j; 37 } 38 } 39 visit[p] = true; 40 used[c++]= minc; 41 for(int j = 0; j < n; j++) 42 { 43 if(!visit[j] && lowc[j] - cost[p][j] > 1e-8) 44 lowc[j] = cost[p][j]; 45 } 46 } 47 } 48 struct nodes 49 { 50 double x,y; 51 }point[N]; 52 53 int main(void) 54 { 55 int i,j,t,m,n; 56 scanf("%d",&t); 57 while(t--) 58 { 59 scanf("%d %d",&m,&n); 60 for(i = 0; i < n; i++) 61 scanf("%lf %lf",&point[i].x,&point[i].y); 62 for(i = 0; i < n; i++) 63 for(j = 0; j < n; j++) 64 cost[i][j] = cost[j][i] = INF; 65 66 for(i = 0; i < n; i++) 67 for(j = i + 1; j <n; j++) 68 { 69 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)); 70 cost[i][j] = cost[j][i] = temp; 71 } 72 memset(used,0,sizeof(used)); 73 c = 0; 74 Prim(n); 75 sort(used,used+c,cmp); 76 printf("%.2f ",used[m-1]);//.2f神坑 77 } 78 return 0; 79 }