acwing-348. 沙漠之王

发表于 分类于 阅读次数： Waline： 本文字数： 842 阅读时长 ≈ 3 分钟

考点

  • 最小生成树
  • 01分数规划
  • 二分

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 50, inf = 0x7f7f7f7f;
const double eps = 1e-6;
int n;
// a代表成本，b代表长度
double a[maxn][maxn], b[maxn][maxn];
double c[maxn][maxn], d[maxn];
bool v[maxn];

struct node {
  int x_, y_, z_;
} p[maxn];

double f(int i, int j) {
  return sqrt((p[i].x_ - p[j].x_) * (p[i].x_ - p[j].x_) +
              (p[i].y_ - p[j].y_) * (p[i].y_ - p[j].y_));
}

bool check(double mid) {
  for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j)
      if (i == j)
        c[i][j] = inf;
      else
        c[i][j] = c[j][i] = a[i][j] - mid * b[i][j];
  memset(v, 0, sizeof(v));
  for (int i = 0; i <= n; ++i) d[i] = inf;
  d[1] = 0;
  double ans = 0;
  for (int k = 1; k <= n; ++k) {
    int x = 0;
    for (int i = 1; i <= n; ++i)
      if (!v[i] && (!x || d[x] > d[i])) x = i;
    v[x] = 1;
    ans += d[x];
    for (int y = 1; y <= n; ++y)
      if (!v[y] && d[y] > c[x][y]) d[y] = c[x][y];
  }
  return ans >= 0;
}

void work() {
  for (int x, y, z, i = 1; i <= n; ++i) {
    cin >> x >> y >> z;
    p[i].x_ = x, p[i].y_ = y, p[i].z_ = z;
  }
  double mx = 0;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      a[i][j] = a[j][i] = abs(p[i].z_ - p[j].z_);
      b[i][j] = b[j][i] = f(i, j);
      mx += a[i][j];
    }
  double l = 0, r = mx;
  while (r - l > eps) {
    double mid = (l + r) / 2;
    if (check(mid))
      l = mid;
    else
      r = mid;
  }
  printf("%.3lf\n", l);
}

int main() {
  while (cin >> n && n) work();
  return 0;
}

思路

01分数规划的模板题。

题意是说有n个点，每个点有(x, y, z)三个属性，(x, y)代表该点坐标，z代表该点高度，

两点i和j之间的欧氏距离保存到b[i][j]，开销等于abs(zi - zj)保存到a[i][j]，点间两两都存在无向边。

设第i条边的开销等于ai，距离等于bi，选任意n - 1条边作为生成树，找出下列式子的最小值： \[ \frac{\sum_{i=1}^n{a_i\cdot x_i}}{\sum_{i=1}^n{b_i\cdot x_i}}\text{，其中}x_i\in \left\{ 0,1 \right\} \] 使用实数二分进行求解。

假设当前有mid小于等于答案ans，由于答案是式子的最小值，你比最小值都小，那么对于任意x都有下式成立： \[ mid\leqslant ans=\frac{\sum{\begin{array}{c} n\\ i=1\\ \end{array}a_ix_i}}{\sum{\begin{array}{c} n\\ i=1\\ \end{array}b_ix_i}}\Longrightarrow \sum{\begin{array}{c} n\\ i=1\\ \end{array}x_i\cdot \left( mid\cdot b_i-a_i \right)}\leqslant 0\text{，对任意}x\text{成立} \] 如果mid大于答案ans，ans只是最小值，只大于最小值并不能说明式子其他解的情况，只能说存在x有下式成立： \[ mid>ans=\frac{\sum{\begin{array}{c} n\\ i=1\\ \end{array}a_ix_i}}{\sum{\begin{array}{c} n\\ i=1\\ \end{array}b_ix_i}}\Longrightarrow \sum{\begin{array}{c} n\\ i=1\\ \end{array}x_i\cdot \left( mid\cdot b_i-a_i \right)}>0\text{，存在}x\text{成立} \] 把上面式子的正负号修改后，整理如下： \[ \begin{cases} mid\leqslant ans\text{时，有}\sum{\begin{array}{c} n\\ i=1\\ \end{array}x_i\cdot \left( a_i-mid\cdot b_i \right)}\geqslant 0\text{，任意}x\text{成立}\\ mid>ans\text{时，有}\sum{\begin{array}{c} n\\ i=1\\ \end{array}x_i\cdot \left( a_i-mid\cdot b_i \right)}<0\text{，存在}x\text{成立}\\ \end{cases} \] 对上述不等式左侧求最小值min即可，也就是最小生成树：

  1. min >= 0，说明mid <= ans，mid不够大，那么mid向右边界移动
  2. min < 0，说明mid > ans，mid大于答案，那么mid向左边界移动
  3. 最后返回左边界l，因为求的是符合条件中的更小值