目录

题目

348. 沙漠之王

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

思路

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

可以转化为

k ⋅ ∑ S − ∑ L = 0 k \cdot \sum S - \sum L = 0 k⋅∑S−∑L=0

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

f ( x ) = ∑ L − x ⋅ ∑ S f(x) = \sum L - x \cdot \sum S f(x)=∑L−x⋅∑S

目标求解使得 f ( x ) = 0 f(x) = 0 f(x)=0的最小的 x x x, 因为 f ( x ) f(x) f(x)具有单调性, 因此可以二分 x 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;
}