POJ2728：Desert King——题解

http://poj.org/problem?id=2728

最小比率生成树。

我们还是01分数规划的思想将边权变为路费用-路长*枚举的答案，跑一遍最小生成树即可。

但是debug的三个小时的我要对出题人说一句。

CNM无良卡常！K算法被卡正常，堆优化Prim都被卡你是什么东西？？？？！！！

#include<cstdio>

#include<cmath>

#include<cstring>

#include<queue>

#include<cctype>

#include<algorithm>

using namespace std;

typedef double dl;

const int N=;

const dl INF=0x7fffffff;

struct node{

    dl w,h;

}e[N][N];

dl dis[N],x[N],y[N],z[N];

int n;

bool vis[N];

inline dl getdis(int i,int j){

    dl X=x[i]-x[j],Y=y[i]-y[j];

    return sqrt(X*X+Y*Y);

}

dl prim(dl mid){

    for(int i=;i<=n;i++)dis[i]=INF,vis[i]=;

    dl ans=;int u=;

    dis[u]=;vis[u]=;

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

    int v;dl minn=INF;

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

        if(vis[j])continue;

        dl w=e[u][j].h-mid*e[u][j].w;

        if(dis[j]>w)dis[j]=w;

        if(minn>dis[j]){

        minn=dis[j];

        v=j;

        }

    }

    vis[v]=;ans+=minn;u=v;

    }

    return ans;

}

int main(){

    while(scanf("%d",&n)!=EOF&&n){

    dl l=,r=;

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

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

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

        e[i][j].w=e[j][i].w=getdis(i,j);

        e[i][j].h=e[j][i].h=fabs(z[i]-z[j]);

        }

    }

    for(int i=;i<=;i++){

        dl mid=(l+r)/;

        if(prim(mid)>=)l=mid;

        else r=mid;

    }

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

    }

    return ;

}