/*
The first line of each test case contains 1 <= S <= 100, the number of satellite channels!
注意：S表示一共有多少个卫星，那么就是有 最多有S-1个通道！ 然后将最小生成树中的后边的 S-1通道去掉就行了！
思路：最小生成树中的第 k 个最小边！
*/
//克鲁斯克尔算法.....
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
double x[800], y[800];
struct node{
int u, v;
double d;
};
bool cmp(node a, node b){
return a.d < b.d;
}
int f[505];
node nd[150000];
double ret[505];
int getFather(int x){
return x==f[x] ? x : f[x]=getFather(f[x]);
}
bool Union(int a, int b){
int fa=getFather(a), fb=getFather(b);
if(fa!=fb){
f[fa]=fb;
return true;
}
return false;
}
int main(){
int n, m;
int t;
scanf("%d", &t);
while(t--){
scanf("%d%d", &m, &n);
for(int i=1; i<=n; ++i){
scanf("%lf%lf", &x[i], &y[i]);
f[i]=i;
}
int cnt=0;
for(int i=1; i<n; ++i)
for(int j=i+1; j<=n; ++j){
nd[cnt].u=i;
nd[cnt].v=j;
nd[cnt++].d=sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
}
sort(nd, nd+cnt, cmp);
int cc=0;
for(int i=0; i<cnt; ++i)
if(Union(nd[i].u, nd[i].v))
ret[cc++]=nd[i].d;
for(int i=0; i<cc; ++i)
cout<<ret[i]<<"fdsf"<<endl;
printf("%.2lf\n", ret[n-m-1]);
}
return 0;
}
//prim算法.......
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double INF = 0x3f3f3f3f*1.0;
double x[800], y[800];
int n, m;
double map[505][505];
int vis[505];
double ret[505];
void prim(){
memset(vis, 0, sizeof(vis));
vis[1]=1;
for(int i=2; i<=n; ++i)
ret[i]=INF;
int root=1, p;
for(int i=1; i<n; ++i){
double minLen=INF;
for(int j=2; j<=n; ++j){
if(!vis[j] && ret[j]>map[root][j])
ret[j]=map[root][j];
if(!vis[j] && minLen>ret[j]){
minLen=ret[j];
p=j;
}
}
root=p;
vis[root]=1;
}
}
int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%d%d", &m, &n);
for(int i=1; i<=n; ++i)
scanf("%lf%lf", &x[i], &y[i]);
for(int i=1; i<n; ++i)
for(int j=i+1; j<=n; ++j)
map[i][j]=map[j][i]=sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
prim();
sort(ret, ret+n+1);
printf("%.2lf\n", ret[n-m+1]);
}
return 0;
}
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3899428.html，如需转载请自行联系原作者
