POJ 2728 Desert King 01分数规划，最优比率生成树

时间：2021-06-11 12:06:14

一个完全图，每两个点之间的cost是海拔差距的绝对值，长度是平面欧式距离，

让你找到一棵生成树，使得树边的的cost的和/距离的和，比例最小

然后就是最优比例生成树，也就是01规划裸题

看这一发：http://blog.csdn.net/sdj222555/article/details/7490797

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<queue>

#include<string.h>

using namespace std;

const int N=1e3+;

const double eps=1e-;

const int INF=0x3f3f3f3f;

int n;

double x[N],y[N],z[N];

double cost[N][N],dis[N][N];

bool vis[N];

double d[N];

double mst(double x) {

    memset(vis,false,sizeof(vis));

    vis[]=true;

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

        d[i]=cost[][i]-x*dis[][i];

    }

    double ret=;

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

      int u;

      double mx=INF;;

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

        if(!vis[j]&&mx>d[j]){

           mx=d[j];

           u=j;

        }

      ret+=mx;

      vis[u]=true;

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

        if(!vis[j]&&d[j]>cost[u][j]-x*dis[u][j])

          d[j]=cost[u][j]-x*dis[u][j];

    }

    return ret;

}

int main() {

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

        if(n==)break;

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

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

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

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

                cost[i][j]=cost[j][i]=fabs(z[i]-z[j]);

            }

        }

        double r=200000.0,l=0.0,mid;

        while(r-l>eps) {

            mid=(l+r)/2.0;

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

            else r=mid;

        }

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

    }

    return ;

}

相关文章