算法竞赛进阶指南.沙漠之王

题目

348. 沙漠之王

算法标签: $01$分数规划, 最小生成树

思路

看题目有要求是构建的渠道的总长度和总成本的比值最小, 形式化的表示
$$k=\frac{\sum L}{\sum S}$$

可以转化为

$$k\cdot \sum S-\sum L=0$$

因为$k$是变化的, 因此可以看做一个函数

$$f(x)=\sum L-x\cdot \sum S$$

目标求解使得$f(x)=0$的最小的$x$, 因为$f(x)$具有单调性, 因此可以二分$x$求出答案

代码

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>using namespace std;const int N = 1010;
const double EPS = 1e-6;struct Village {int x, y, z;
} pos[N];struct Edge {int u, v;double dis, w;
} edges[N * N / 2];int n, idx;
int p[N];double calc(const Village& a, const Village& b) {int dx = a.x - b.x;int dy = a.y - b.y;return sqrt(dx * dx + dy * dy);
}int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}bool check(double mid) {for (int i = 0; i < n; ++i) p[i] = i;vector<pair<double, pair<int, int>>> vec;for (int i = 0; i < idx; ++i) {double val = edges[i].w - mid * edges[i].dis;vec.emplace_back(val, make_pair(edges[i].u, edges[i].v));}sort(vec.begin(), vec.end());double res = 0;for (const auto& edge : vec) {int u = edge.second.first;int v = edge.second.second;int fa1 = find(u);int fa2 = find(v);if (fa1 != fa2) {p[fa2] = fa1;res += edge.first;}}return res <= 0;
}void solve() {idx = 0;for (int i = 0; i < n; ++i) {cin >> pos[i].x >> pos[i].y >> pos[i].z;}for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {double dist = calc(pos[i], pos[j]);double cost = abs(pos[i].z - pos[j].z);edges[idx++] = {i, j, dist, cost};}}double l = 0, r = 1e6;while (r - l > EPS) {double mid = (l + r) / 2;if (check(mid)) r = mid;else l = mid;}cout << fixed << setprecision(3) << l << endl;
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);while (cin >> n, n) solve();return 0;
}