POJ 2728-Desert King

Description

给你三维空间n个点，定义两点间连边的花费为海拔之差，边的长度为平面距离。求一种生成树方案使得选的边的总花费/总长度最小

分数规划。
也就是代表只能选n-1条使原图联通的边使得比值最小。我们二分比值，计算如果小于0，说明有更优解。`
完全图最小生成树还是用prim吧。不然kruskalO(mlogm)多了个logn。
另外二分区间的初值可不是[0,1]啊。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
double dis[1100],px[1100],py[1100],pz[1100],mcos[1100][1100],mlen[1100][1100];
int n;
bool v[1100];
bool check(double x)
{
    for(int i=0;i<=n;i++) dis[i]=100000000;
    memset(v,0,sizeof(v));
    dis[1]=0; int k; double sum=0;
    for(int i=1;i<=n;i++)
    {
        k=0;
        for(int j=1;j<=n;j++) if(!v[j]&&dis[j]<dis[k]) k=j;
        v[k]=1; sum+=dis[k];
        for(int j=1;j<=n;j++) if(!v[j]) dis[j]=min(dis[j],mcos[k][j]-x*mlen[k][j]);
    }
    return sum<0;
}
int main()
{
    while(scanf("%d",&n))
    {
        if(!n) break;
        for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&px[i],&py[i],&pz[i]);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                if(i!=j)
                {
                    mlen[i][j]=sqrt((px[i]-px[j])*(px[i]-px[j])+(py[i]-py[j])*(py[i]-py[j]));
                    mcos[i][j]=fabs(pz[i]-pz[j]);
                }
        }
        double l=0,r=1000000000,mid;
        while(1e-5<r-l)
        {
            mid=(l+r)/2;
            if(check(mid)) r=mid;
            else l=mid;
        }
        printf("%.3lf\n",r);
    }
    return 0;
}