问题描述

给你在平面直角坐标中的n个点,以及点的高度。两个点的高度之差代表该边的成本,两点的欧几里得距离代表该边的长度(这个可以看成一个完全图)。你需要找出一个成本之和/长度之和最小的生成树。

输入

有多组数据,每组数据第一行包含n(以n=0结束输入)。
接下来n行,每行有包含3个数,表示一个点的横坐标,纵坐标和高度。

输出

输出长度之和/成本之和的最小值,保留小数点后3位。

思路

看到求其中式子的最值,这就是01分数规划问题,这道题就属于01分数规划中比较水的

首先二分答案,然后将图上所有边权改为成本-(答案* 该边长度)。然后找一棵最小生成树,若它的边权之和小于0则r=mid,否则l=mid。直到答案符合精度要求。

其实还有一种迭代的方法,比二分优很多。还是同样的思路,只是代码作了一点小的该动。

细节

  1. 变量都要用double
  2. 二分精度要1e-6 然而我不知道为什么

代码

二分的代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAXN 1005
#define eps 1e-6
using namespace std;

struct Graph {double cost, dis, val;} mmp[MAXN][MAXN];

int n, x[MAXN], y[MAXN], z[MAXN];
double dis[MAXN];
bool vis[MAXN];

double cal(int i, int j)
{
    return sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}

void init()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<i; j++)
        {
            mmp[i][j].dis=mmp[j][i].dis=cal(i, j);
            mmp[i][j].cost=mmp[j][i].cost=abs((double)z[i]-z[j]);
        }
    }
}

double prim(double mid)
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<i; j++)
            mmp[i][j].val=mmp[j][i].val=mmp[i][j].cost-mid*mmp[i][j].dis;
    for(int i=1; i<=n; i++)
            dis[i]=mmp[1][i].val, vis[i]=0;
    double ans=0; 
    dis[1]=0; vis[1]=1;
    for(int i=1; i<n; i++)
    {
        int x=0;
        for(int j=1; j<=n; j++)
            if(!vis[j] && (x==0 || dis[j]<dis[x])) x=j;
        if(x==0) break;
        vis[x]=1; ans+=dis[x];
        for(int j=1; j<=n; j++)
            if(!vis[j]) dis[j]=min(dis[j], mmp[x][j].val);
    }
    return ans;
}

int main()
{
    while(scanf("%d", &n) && n!=0)
    {
        for(int i=1; i<=n; i++) scanf("%d%d%d", &x[i], &y[i], &z[i]);
        init();
        double l=0, r=1000000;
        while(l+eps<r)
        {
            double mid=(l+r)/2;
            if(prim(mid)>=0) l=mid;
            else r=mid;
        }
        printf("%.3f\n", (l+r)/2);
    } 
}

迭代的代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAXN 1005
#define eps 1e-4
using namespace std;

struct Graph {double cost, dis, val;} mmp[MAXN][MAXN], dis[MAXN];

int n, x[MAXN], y[MAXN], z[MAXN];
bool vis[MAXN];

double cal(int i, int j)
{
    return sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}

void init()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<i; j++)
        {
            mmp[i][j].dis=mmp[j][i].dis=cal(i, j);
            mmp[i][j].cost=mmp[j][i].cost=abs((double)z[i]-z[j]);
        }
    }
}

double prim(double mid)
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<i; j++)
            mmp[i][j].val=mmp[j][i].val=mmp[i][j].cost-mid*mmp[i][j].dis;
    for(int i=1; i<=n; i++)
        dis[i]=mmp[1][i], vis[i]=0;
    dis[1].val=0; vis[1]=1;
    double c=0, l=0;
    for(int i=1; i<n; i++)
    {
        int x=0;
        for(int j=1; j<=n; j++)
            if(!vis[j] && (x==0 || dis[j].val<dis[x].val)) x=j;
        if(x==0) break;
        vis[x]=1;
        c+=dis[x].cost; l+=dis[x].dis;
        for(int j=1; j<=n; j++)
            if(!vis[j] && dis[j].val>mmp[x][j].val) dis[j]=mmp[x][j];
    } 
    return c/l;
}

int main()
{
    while(scanf("%d", &n) && n!=0)
    {
        for(int i=1; i<=n; i++) scanf("%d%d%d", &x[i], &y[i], &z[i]);
        init();
        double a=0, b=0;
        while(1)
        {
            a=prim(b);
            if(abs(a-b)<eps) break;
            b=a;
        }
        printf("%.3f\n", a);
    } 
}

2 对 “POJ2728 Desert King [分数规划+最小生成树]”的想法;

发表评论

邮箱地址不会被公开。 必填项已用*标注