POJ 2728 Desert King [最优比率生成树]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1005;
const double eps=1e-4,INF=1e9;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();}
    return x*f;
}
int n;
double c[N][N],d[N][N],w[N][N];
struct Position{
    double x,y,z;
}a[N];
double mn[N];
bool vis[N];
bool check(double mid){//printf("check %lf\n",mid);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j) 
            w[i][j]=c[i][j]-d[i][j]*mid;
    memset(vis,0,sizeof(vis));memset(mn,127,sizeof(mn));mn[1]=0;
    for(int i=1;i<=n;++i){
        int k=0;
        for(int j=1;j<=n;++j) if(!vis[j]&&mn[j]<mn[k]) k=j;
        vis[k]=1;
        for(int j=1;j<=n;++j) if(!vis[j]&&w[j][k]<mn[j]) mn[j]=w[j][k];
    }
    double re=0;
    for (int i=1;i<=n;++i) re+=mn[i];
    return re<0;
}

void solve(){
    double l=0,r=1e2;
    while(r-l>eps){
        double mid=(l+r)/2.0;
        if(check(mid)) r=mid;
        else l=mid;
    }
    printf("%.3f\n",l);
}
int main(){
    freopen("in","r",stdin);
    while(scanf("%d",&n)!=EOF&&n){
        for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].z=read();
        if(n==1) {puts("0.000");continue;}
        for(int i=1;i<=n;i++) 
            for(int j=1;j<=n;++j) 
                c[i][j]=abs(a[i].z-a[j].z),
                d[i][j]=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
        solve();
    }
}