题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

//一开始用的vector+优先队列prim着实是蠢，每次建图都要n方，时间复杂度与朴素prim一样但是由于
//vector动态开空间会消耗大量时间，而且是多样例而超时
//最后借鉴了一下第二个题解的方法写了个朴素prim

//最优比率树问题，显然01规划是必须的，数论里的一点儿知识，很简单
//对于化简式子之后，建好的图，我们要确定是跑最小生成树还是最大生成树
//设w为花费 l为长度
//题目要求w/l的最小值，我们设z为w/l的最小值
//       w / l = z 化简可得w=z*l，再次化简w-z*l=0
//      对于这个式子，z为最小值时满足式子为0，反过来显然当w-z*l为0时，z可以取到最小
//      现在假设我们不知道z的具体值，我们要想办法让式子等于0，从而求得z的具体值
//      我们发现这个式子显然时随着z的减小而递增的，所以我们二分z，当z越小时，式子的值越大，而
//      我们想让式子为0，所以我们应该选取图中的所有较小的边组成  最小生成树，即应该跑最小生成树
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f;
const double dinf = 999999999999.0;
#define p2(a) (a*a)
struct point{
    double x, y, z;
}a[1005];
int n;
struct node{
    ll x; double w;
    friend bool operator <(node a, node b){
        return a.w > b.w;
    }
};
vector<node> p[1005];
double dis(int x, int y){
    return sqrt((a[x].x - a[y].x)*(a[x].x - a[y].x) + (a[x].y - a[y].y)*(a[x].y - a[y].y));
}
double d[1005];
bool vis[1005];

double prim(double mid){
    double ans = 0;
    for (int i = 1; i <= n; i++){
        vis[i] = 0;
        d[i] = inf;
    }
    d[1] = 0;
    for (int i = 1; i <= n; i++){
        int x = 0;
        for (int j = 1; j <= n; j++){
            if (!vis[j] && (x == 0 || d[j] < d[x]))
                x = j;
        }
        vis[x] = 1;
        ans += d[x];
        for (int k = 1; k <= n; k++){
            if (!vis[k]){
                d[k] = min(d[k], abs(a[x].z - a[k].z) - mid*dis(x, k));
            }
        }
    }
    return ans;
}

int main(){

    while (cin >> n){
        if (n == 0)break;
        for (int i = 1; i <= n; i++){
            scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].z);
        }
        double l = 0;
        double r = 999999.0;
        while (abs(r - l) > 0.0000001){
            double mid = l + (r - l) / 2;
            if (prim(mid) >= 0){
                l = mid;
            }
            else{
                r = mid;
            }
        }
        printf("%.3f\n", (l + r) / 2);
    }


}