Desert King

题目描述

David the Great has just become the king of a desert country. To win the respect of his people, he decided to build channels all over his country to bring water to every village. Villages which are connected to his capital village will be watered. As the dominate ruler and the symbol of wisdom in the country, he needs to build the channels in a most elegant way.

After days of study, he finally figured his plan out. He wanted the average cost of each mile of the channels to be minimized. In other words, the ratio of the overall cost of the channels to the total length must be minimized. He just needs to build the necessary channels to bring water to all the villages, which means there will be only one way to connect each village to the capital.

His engineers surveyed the country and recorded the position and altitude of each village. All the channels must go straight between two villages and be built horizontally. Since every two villages are at different altitudes, they concluded that each channel between two villages needed a vertical water lifter, which can lift water up or let water flow down. The length of the channel is the horizontal distance between the two villages. The cost of the channel is the height of the lifter. You should notice that each village is at a different altitude, and different channels can’t share a lifter. Channels can intersect safely and no three villages are on the same line.

As King David’s prime scientist and programmer, you are asked to find out the best solution to build the channels.

题意概述

空间中有$N$个点。定义点$(x_0, y_0, z_0)$与点$(x_1, y_1, z_1)$之间的距离为$\sqrt{(x_0-x_1)^2+(y_0-y_1)^2}$，在它们之间连边的花费为$|z_0-z_1|$。要使得任意两点之间恰有一条路径，求总花费除以总距离的最小值。

数据范围：$2 \le N \le 1000$。

算法分析

假设我们连边的集合为$S$，最小值为$k$。令$l_i$表示边的长度，$c_i$表示边的花费。那么有

$$
{\sum_{i \in S} c_i \over \sum_{i \in S} l_i} \ge k
$$

移项得

$$
\begin{align}
\sum_{i \in S} c_i &\ge k\sum_{i \in S} l_i \\
\sum_{i \in S} (c_i-kl_i) &\ge 0
\end{align}
$$

不管怎么连边，这个不等式都成立。因此只要可以判断是否存在不满足不等式的连边方案，就可以对$k$进行二分。我们给每条边$i$赋权$c_i-kl_i$，那显然最坏情况就是新图的最小生成树。

还有一种基于迭代的方法。在求出最小生成树后，将$k$赋值为这棵最小生成树的总花费除以总距离，继续迭代，直到满足精度要求为止。

最小生成树需要用 Prim 来求，否则容易超时。

代码

/*
 * Good news from afar can bring you a welcome visitor.
 */

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

#define sqr(x) (1. * (x) * (x))

static int const N = 1005;
static double const EPS = 1e-5;
int fa[N], vis[N], pre[N];
double dist[N], mp[N][N];
struct Point {
  int x, y, z;
} p[N];

int main() {
  int n;
  for (scanf("%d", &n); n; scanf("%d", &n)) {
    for (int i = 1; i <= n; ++i)
      scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);
    double ans = 0;
    for (;;) {
      for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
          if (i != j)
            mp[i][j] = abs(p[i].z - p[j].z) -
                       ans * sqrt(sqr(p[i].x - p[j].x) + sqr(p[i].y - p[j].y));
      double cost = 0, len = 0;
      memset(vis, 0, sizeof vis), vis[1] = 1;
      for (int i = 2; i <= n; ++i)
        dist[i] = mp[1][i], pre[i] = 1;
      for (int i = 2; i <= n; ++i) {
        int pos = 0;
        double mn = 1e15;
        for (int j = 1; j <= n; ++j)
          if (!vis[j] && dist[j] < mn)
            mn = dist[pos = j];
        vis[pos] = 1, cost += abs(p[pos].z - p[pre[pos]].z),
        len +=
            sqrt(sqr(p[pos].x - p[pre[pos]].x) + sqr(p[pos].y - p[pre[pos]].y));
        for (int j = 1; j <= n; ++j)
          if (!vis[j] && mp[pos][j] < dist[j])
            dist[j] = mp[pos][j], pre[j] = pos;
      }
      if (abs(cost / len - ans) < EPS) {
        printf("%.3lf\n", ans);
        break;
      }
      ans = cost / len;
    }
  }
  return 0;
}