題目鏈接

相關證明在另一篇簡書上

題意就不說了,兩個村莊之間的距離為歐幾里得距離,花費是兩個村莊的海拔高度.
求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]數(shù)組.
    }
    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);
    }

}