题目描述

求解最优比率生成树

为什么求解最小生成树来判断最小比率

献个丑，可能会有人和我一样不知道为什么求解的是最小生成树吧，希望对这些人有帮助

首先分数规划不过多描述，这里要求解的是一个函数
$$Min Z=∑W/∑L$$

转化一下就是 $$∑W-Z*∑L = 0$$

即 $$F(X) = ∑W-X*∑L$$

这个函数是个单调递减函数，随着$x$的增大而减少

目标是求解使$F(x)=0$的最小的$x$

相同的$x$值，对于不同的生成树来说，$f(x)$也不完全相同

若要使$x$取最小值，则不能存在一个生成树$y$使得$fy(x)<0$,否则对于这个生成树$y$来说，他的比率一定小于当前$x$，那么$x$可以继续减小。

换句话说就是要满足任意一个生成树的$f(x)>=0$，这样$x$无法继续减小，得到最小的$x$

要满足$f(x)>=0$恒成立，则必须满足最小生成树权值和>=0,因为他是最小的了

所以使用最小生成树来求解

如果最小生成树大于0,所有的生成树都满足$f(x)>0$,尝试增加x得到$f(x)=0$
否则，有生成树不满足这个条件，那么$x$一定要减少来使所有$f(x)>=0$

 //#pragma GCC optimize(3)
// #pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ALL(x) (x).begin(),(x).end()
#define mem(x,y) memset((x),(y),sizeof(x))
#define Discertize(x) sort(ALL(x)),x.erase(unique(x.begin(),x.end()),x.end());
#define SZ(x) ((int)(x).size())
#define P2(x) ((x)*(x))
#define P pair<int,int>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
const int maxm = 2e5 + 10;
const int mod = 1e9 + 7;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const double Dinf = 1e18;
const double eps = 1e-6;
template<typename S, typename T> inline bool Min(S &a, const T &b){ return a > b ? a = b, true : false; }
template<typename S, typename T> inline bool Max(S &a, const T &b){ return a < b ? a = b, true : false; }
template<typename S, typename T> inline void Adm(S &a, const T &b){ a = (a + b) % mod; if (a < 0) a += mod; }
template<typename S, typename T> inline void Mum(S &a, const T &b){ a = 1LL * a * b % mod; }
template<typename T> inline T Gcd(T a, T b){ while (b){ T t = b; b = a % b; a = t; }return a; }
template<typename T> inline int BitCnt(T x){ int cnt = 0; while (x)++cnt, x &= x - 1; return cnt; }
template<typename T> inline bool IsPri(T x) { if (x < 2) return false; for (T i = 2; i * i <= x; ++i) if (x % i == 0) return false; return true; }
inline ll qpow(ll a, ll n){ ll t = 1; while (n){ if (n & 1)t = t * a % mod; a = a * a % mod, n >>= 1; }return t%mod; }
void p_bit(ll x){cout<<bitset<32>(x)<<':'<<x<<endl;}

int x[maxn],y[maxn],w[maxn];
double dis[maxn];
bool vis[maxn];
double calc(int a,int b){
    return sqrt(P2(x[a]-x[b]) + P2(y[a]-y[b]));
}
int n;
bool check(double mid){
     fill(dis,dis+n+1,Dinf);
     fill(vis,vis+n+1,0);
     dis[1]=0;
     double ans=0;
     for(int i=1;i<=n;i++){
        double mx=Dinf;
        int k=1;
        for(int j=1;j<=n;j++)
            if(!vis[j] && mx>dis[j])
                mx=dis[j],k=j;
        vis[k]=1;
        ans += dis[k];
         for(int j=1;j<=n;j++){
            if(!vis[j] && dis[j] >  fabs(w[k]-w[j])- mid* calc(k,j) + eps)
                dis[j]= fabs(w[k]-w[j]) - mid* calc(k,j);
        }
     }
    return ans>=0.0;
}
int main(){

    /*
        x=w/l -> w-l*x =0
        f(x) = w-l*x;
        将边权更改为w-l*x来求生成树

       因为f(x)是个单调递减函数,随着x的增大而减少
       对于任意一个生成树如果
        f(x)>0        则   l需要增大
        f(x)<0        否则 l需要减小

       若要满足f(x)==0恒成立
       1.若要x取最大值，则不能存在任意一个生成树f(x)>0,否则x还能继续增大,即任意生成树f(x)<=0
         若存在一个生成树f(x)>0，则那个生成树的比率一定大于当前x,w/l > x -> w-l*x > 0
       2.若要x取最小值，则不能存在任意一个生成树f(x)<0,否则x还能继续减小,即任意生成树f(x)>=0
         若存在一个生成树f(x)<0，则那个生成树的比率一定小于当前x,w/l < x -> w-l*x < 0

       若要满足f(x)>0恒成立，则最小生成树>0
       若要满足f(x)<0恒成立，则最大生成树<0

        此题目求解最小的x值，也就是检查是否所有的生成树f(x)>=0，即最小生成树>=0

        如果最小生成树大于0,所有的生成树都满足f(x)>0,尝试增加x得到f(x)=0
        否则，有生成树不满足这个条件，那么x一定要减少来使所有f(x)>=0

       kur边数较多，复杂度(mlog*log)排序加二分，过不去
       使用prim算法
    */
    while(~scanf("%d",&n),n){
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&x[i],&y[i],&w[i]);
        double l=0,r=10000001.0;
        double ans;
        while( (r-l) > eps){
            double mid=(l+r)/2;
            if(check(mid))ans=mid,l=mid;
            else r=mid;
        }
        printf("%.3f\n",ans);
    }
    return 0;
}