这题数据量较大。普通的求MST是会超时的。

d[i]=cost[i]-ans*dis[0][i]

据此二分。

但此题用Dinkelbach迭代更好

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 1010

double mp[N][N],c[N][N],x[N],y[N],z[N],e[N][N],d[N];

int vis[N],n;

inline double prim(double mid)

{

    double tmp,ans=0;

    for(int i=0;i<n;i++)

    {

        vis[i]=0;

        for(int j=0;j<i;j++)

            e[i][j]=e[j][i]=c[i][j]-mid*mp[i][j];

    }

    for(int i=1;i<n;i++)

        d[i]=e[0][i];

    d[0]=0;vis[0]=1;

    for(int i=1;i<n;i++)

    {

        int p;

        tmp=100000000;

        for(int j=0;j<n;j++)

        {

            if(!vis[j]&&d[j]<tmp)

            {

                p=j;

                tmp=d[j];

            }

        }

        ans+=tmp;

        vis[p]=1;

        for(int j=0;j<n;j++)

        {

            if(!vis[j]&&e[j][p]<d[j])

                d[j]=e[j][p];

        }

    }

    return ans;

}

int main()

{

    int i,j;

    double le,ri,mid;

    while(scanf("%d",&n)&&n)

    {

        for(i=0;i<n;i++)

            scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);

        for(i=0;i<n;i++)

            for(j=0;j<i;j++)

            {

                mp[i][j]=mp[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

                c[i][j]=c[j][i]=z[i]>z[j]?z[i]-z[j]:z[j]-z[i];

            }

        le=0;ri=1001;//不开心。。这样才干水过

        while(ri-le>1e-5)

        {

            mid=(le+ri)/2.0;

         //   printf("prim:%lf\n",prim(0,mid));

            if(prim(mid)>0)

                le=mid;

            else ri=mid;

        }

        printf("%.3f\n",mid);

    }

    return 0;

}