poj2349:http://poj.org/problem?id=2349
题意：有卫星电台的城市之间可以任意联络。没有卫星电台的城市只能和距离小于等于D的城市联络。告诉你卫星电台的个数S，让你求最小的D.
题解： 生成最小生成树，去掉最长的S条边后，剩下最长的边就是D.也就是求最小生成树中第S+1长的边。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cmath> 6 #define INF 100000000.0 7 using namespace std; 8 int cas,x,y,top; 9 int n,s; 10 double lowcost[502],ans[502],g[502][502]; 11 struct Node{ 12 int x; 13 int y; 14 }node[103]; 15 double juli(Node a,Node b ){ 16 return sqrt(((double)a.x-b.x)*(a.x-b.x)+((double)a.y-b.y)*(a.y-b.y)); 17 } 18 void prim(int v0){ 19 top=0; 20 for(int i=1;i<=n;i++){ 21 lowcost[i]=g[v0][i]; 22 } 23 lowcost[v0]=-1; 24 for(int i=1;i<n;i++){ 25 double min=INF; 26 int v=-1; 27 for(int j=1;j<=n;j++){ 28 if(lowcost[j]!=-1&&lowcost[j]<min){ 29 min=lowcost[j]; 30 v=j; 31 } 32 } 33 if(v!=-1){ 34 ans[top++]=lowcost[v]; 35 lowcost[v]=-1; 36 for(int k=1;k<=n;k++){ 37 if(lowcost[k]!=-1&&g[v][k]<lowcost[k]){ 38 lowcost[k]=g[v][k]; 39 } 40 } 41 } 42 } 43 } 44 void solve(){ 45 sort(ans,ans+top); 46 printf("%.2f ",ans[top-s]); 47 } 48 int main(){ 49 scanf("%d",&cas); 50 while(cas--){ 51 scanf("%d%d",&s,&n); 52 for(int i=1;i<=n;i++){ 53 scanf("%d %d",&node[i].x,&node[i].y); 54 } 55 for(int i=1;i<=n;i++) 56 for(int j=i+1;j<=n;j++){ 57 g[i][j]=g[j][i]=juli(node[i],node[j]); 58 // printf("%.2f ",g[i][j]); 59 } 60 for(int i=1;i<=n;i++) 61 for(int j=1;j<=n;j++){ 62 if(i==j)g[i][j]=0; 63 else if(g[i][j]==0)g[i][j]=INF; 64 } 65 prim(1); 66 solve(); 67 } 68 }