AcWing 348 Dessert King

题目描述

大卫大帝刚刚建立了一个沙漠帝国，为了赢得他的人民的尊重，他决定在全国各地建立渠道，为每个村庄提供水源。

与首都相连的村庄将得到水资源的浇灌。

他希望构建的渠道可以实现单位长度的平均成本降至最低。
换句话说，渠道的总成本和总长度的比值能够达到最小。

他只希望建立必要的渠道，为所有的村庄提供水资源，这意味着每个村庄都有且仅有一条路径连接至首都。

他的工程师对所有村庄的地理位置和高度都做了调查，发现所有渠道必须直接在两个村庄之间水平建造。
由于任意两个村庄的高度均不同，所以每个渠道都需要安装一个垂直的升降机，从而使得水能够上升或下降。
建设渠道的成本只跟升降机的高度有关，换句话说只和渠道连接的两个村庄的高度差有关。
需注意，所有村庄（包括首都）的高度都不同，不同渠道之间不能共享升降机。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含整数 $N$，表示村庄（包括首都）的总数目。

接下来 $N$ 行，每行包含三个整数 $x，y，z$，描述一个村庄的地理位置，$(x,y)$ 为该村庄的位置坐标，$z$ 为该村庄的地理高度。

第一个被描述的村庄即为首都。

当输入一行为 $0$ 时，表示输入终止。

输出格式

每组数据输出一个结果，每个结果占一行。
结果为一个保留三位小数的实数，表示渠道的总成本和总长度的比值的最小值。

数据范围

$2 ≤ N ≤ 1000,$
$0 ≤ x,y < 10000,$
$0 ≤ z ≤ 10000000$

样例解释

$blablabla$

思路概要

这道题显然是一道最优比例生成树问题。
首先，根据题目要求，各个村庄到首都只有一条路径，确定这是一棵最小生成树，其次，要求花费与道路长度之比最小。由于按照贪心直接按比例排序不具有完全正确性，所以这时我们列出表达式，不难联想到$0/1$分数规划问题的做法，那么由此即可编写代码开始求解。

代码思路

利用$0/1$分数规划的一般求解方法，以二分渐趋的形式，逼近答案，并将上次检索到的解保存下来，不断在已知最优的基础上建边，直至误差小于$eps$。

代码附上

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e3 + 20, M = 5e5 + 20;
const double eps = 1e-5;
typedef double Db;

int n, cnt, f[N];
struct Nod{
    Db x, y, high;
    #define x(i) nod[i].x
    #define y(i) nod[i].y
    #define h(i) nod[i].high
}nod[N];

struct Edge{
    int s, t;
    Db len, cost;
    #define s(i) e[i].s
    #define t(i) e[i].t
    #define l(i) e[i].len
    #define c(i) e[i].cost
    bool operator <(const Edge &t)
      const{ return cost < t.cost; }
}e[M];

int inline find(int x){ return f[x] == x ? x : f[x] = find(f[x]); }

Db inline getl(Nod a, Nod b){
    return sqrt(fabs(a.x - b.x) * fabs(a.x - b.x) + fabs(a.y - b.y) * fabs(a.y - b.y));
}

Db inline getc(Nod a, Nod b, Db now, Db len){ return fabs(a.high - b.high) - now * len;}

int main()
{
    while(scanf("%d", &n), n)
    {
        cnt = 0;
        for(int i = 1; i <= n; i ++) 
            scanf("%lf%lf%lf", &x(i), &y(i), &h(i));

        Db ans = 0, now = 0;
        while(true)
        {
            ans = now, cnt = 0;
            for(int i = 1; i <= n; i ++){
                f[i] = i;
                for(int j = i + 1; j <= n; j ++)
                {
                    Db len = getl(nod[i], nod[j]);
                    Db c = getc(nod[i], nod[j], now, len);
                    e[++ cnt] = {i, j, len, c};
                }
            }

            sort(e + 1, e + 1 + cnt);
            Db totc = 0, totl = 0;
            for(int i = 1; i <= cnt; i ++)
            {
                int s = find(s(i)), t = find(t(i));
                if(s == t) continue;
                f[s] = t, totl += l(i);
                totc += fabs(h(s(i)) - h(t(i)));
            }

            now = totc / totl;
            if(fabs(ans - now) < eps) break;
        }

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

    return 0;
}