最优比率生成树 --- POJ --- 2728

题目链接

相关证明在另一篇简书上

题意就不说了,两个村庄之间的距离为欧几里得距离,花费是两个村庄的海拔高度.
求sigma(cost[i])/sigma(lenth[i]).
思路:
还是二分答案,使得答案不断接近我们要的那个答案.具体看代码吧.

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<stack>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
#define mod 1000000007
using namespace std;
const int maxn=1e3+5;
const db eps=1e-7;
const db inf=1e9;
int n;
db mapp[maxn][maxn];
db low[maxn];
int vis[maxn];
struct point
{
    int x,y,z;
}s[maxn];

db cal(int m,int n)
{
    return sqrt(1.0 * (s[m].x-s[n].x)*(s[m].x-s[n].x)+1.0 * (s[m].y-s[n].y)*(s[m].y-s[n].y));
}

db prim(int fa,db mid)
{
    db sum=0;
    for(int i=1;i<=n;i++){
        low[i] = abs(s[fa].z-s[i].z)*1.0-mid*mapp[fa][i];   //d[i]数组.
    }
    CLR(vis);
    //cout << "BUG?" << endl;
    vis[fa]=1;
    for(int i=1;i<n;i++){  //找点肯定只用找n-1个点啊.
        db minn=inf;
        int v=-1;

        for(int j=1;j<=n;j++){
            if(!vis[j] && minn>low[j]){
                v=j;
                minn=low[j];
            }
            //cout << "BUG?" << " " << j << " " << n << endl;
        }

        if(v!=-1){
            sum += minn;
            vis[v]=1;
            for(int j=1;j<=n;j++){
                db tmp=abs(s[v].z-s[j].z)*1.0-mid*mapp[v][j];
                if(!vis[j] && low[j] > tmp)
                    low[j]= tmp;
            }
        }
    }
    //cout << "BUG?" << endl;
    return sum;
}

int main()
{
    while(~scanf("%d",&n) && n){
        for(int i=1;i<=n;i++){
            scanf("%d %d %d",&s[i].x,&s[i].y,&s[i].z);
        }
        CLR(mapp);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                mapp[i][j] =  cal(i,j);
            }
        }           // 不断测试,r=100是最好的.
        db l=0,r=100.0,mid;    //二分的范围自己定,总之越大当然肯定能出答案,但是时间相应也会增长,所以选择一个合理的范围是很重的.
        while(r-l>eps){
            mid = (r+l) / 2 ;
            if(prim(1,mid) >= 0 ) l=mid;
            else r=mid;
        }
        printf("%.3f\n",r);
    }

}