易错点：
- double类型不初始化为0就爆炸.
- 每次prim前需要先从首都向每个村庄加边.
- "长度"指二维欧氏距离.
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=2e3,INF=1<<30;
struct village{
int x,y,z;
}villages[MAXN];
double getDis(village a,village b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.z-b.z)*(a.z-b.z));
}
int n,pre[MAXN];
bool vis[MAXN];
double minw[MAXN],cost[MAXN][MAXN],len[MAXN][MAXN];
double prim(double k){
memset(vis,0,sizeof(vis));
vis[1]=1;
for(int i=2;i<=n;i++){
minw[i]=cost[1][i]-len[1][i]*k;
pre[i]=1;
}
double Cost,Len;
Cost=Len=0;//不初始化就爆炸
for(int i=1;i<=n;i++){
double nowMin=INF;
int nowV=0;
for(int j=1;j<=n;j++){
if(!vis[j]&&minw[j]<nowMin){
nowMin=minw[nowV=j];
}
}
vis[nowV]=1;
Cost+=cost[pre[nowV]][nowV],Len+=len[pre[nowV]][nowV];
for(int j=1;j<=n;j++){
double tmp=cost[nowV][j]-k*len[nowV][j];
if(!vis[j]&&tmp<minw[j]){
minw[j]=tmp;
pre[j]=nowV;
}
}
}
return Cost/Len;
}
void init(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cost[i][j]=fabs(villages[i].y-villages[j].y);
len[i][j]=getDis(villages[i],villages[j]);
}
}
}
int main(){
while(~scanf("%d",&n)){
if(n==0)break;
for(int i=1;i<=n;i++){
int x,y,z;
scanf("%d%d%d",&villages[i].x,&villages[i].z,&villages[i].y);
}
init();
double a,b;
while(1){
b=prim(a);
if(fabs(b-a)<1e-4)break;
a=b;
}
printf("%.3f
",a);
}
return 0;
}