POJ 2728（最优比率生成树+01规划）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<cstring>
#include<map>
#include<stack>
#include<set>
#include<vector>
#include<algorithm>
#include<string.h>
typedef long long ll;
typedef unsigned long long LL;
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=0.0000000001;
const int N=100000+10;
const int MAX=1000+10;
int vis[N];
double x[N],y[N],z[N];
double w[MAX][MAX],v[MAX][MAX];
double low[N];
int n;
double fun(double a,double b,double c,double d){
    double ans=(a-c)*(a-c)+(b-d)*(b-d);
    return sqrt(ans);
}
int prime(double x){
    double sum=0;
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++)low[i]=v[0][i]-x*w[0][i];
    vis[0]=1;
    for(int i=0;i<n;i++){
        int k;
        double maxx=INF*1.0;
        for(int j=0;j<n;j++)if(vis[j]==0&&low[j]<maxx){
            maxx=low[j];
            k=j;
        }
        if(maxx==1.0*INF)break;
        sum=sum+maxx;
        vis[k]=1;
        for(int j=0;j<n;j++)
        if(vis[j]==0&&low[j]>v[k][j]-x*w[k][j])
        low[j]=v[k][j]-x*w[k][j];
    }
    if(sum>0)return 1;
    else
        return 0;
}
int main(){
    while(scanf("%d",&n)!=EOF){
        if(n==0)break;
        double maxx=0;
        double minn=INF*1.0;
        for(int i=0;i<n;i++)scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);
        for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++){
            double t=fun(x[i],y[i],x[j],y[j]);
            w[i][j]=w[j][i]=t;
            v[i][j]=v[j][i]=fabs(z[i]-z[j]);
            maxx=max(v[i][j],maxx);
            minn=min(minn,t);
        }
        double low=0.0;
        double high=maxx/minn;
        double ans;
        while(low+eps<high){
            double mid=(low+high)/2;
            if(prime(mid)){
                ans=mid;
                low=mid;
            }
            else
                high=mid;
        }
        printf("%.3f\n",ans);
    }
}