POJ2728 Desert King（最优比率生成树）

题意：

有\(n\)个村庄，村庄在不同坐标和海拔，现在要对所有村庄供水，只要两个村庄之间有一条路即可，建造水管距离为坐标之间的欧几里德距离，费用为海拔之差，现在要求方案使得费用与距离的比值最小。\(n<=1000\)

思路：

经典的01分数规划求解最优比率生成树，在此题中稠密图采用暴力Prim求解。

时间复杂度：\(O(n^2*logn)\).

Code:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cassert>
//#include<bits/stdc++.h>
#define debug(x) cout<<#x<<" :"<<x<<endl
using namespace std;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define SZ(x) ((int)(x).size())
#define eps 1e-6
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1e9+7;
ll powmod(ll a,ll b,ll mod1) {ll res=1;a%=mod1; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod1;a=a*a%mod1;}return res;}
const int maxn=2e5+10;
const int MAXN=2e5+10;
int q[maxn];
ll n,m;
ll a[maxn];
ll b[maxn];
int dp[10][4001];
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
typedef pair<double,int> pdi;

struct point{
    double x,y;
    double high;
}q1[maxn];

int head[maxn],edge_num;
double length(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double high(point a,point b){
    double ans=fabs(a.high-b.high);
    return ans;
}
double D[maxn];int vis[maxn];
double len[2001][2001];
double cost[2001][2001];
int check(double ans){
    for(int i=1;i<=n;++i){
        D[i]=1e18;
        vis[i]=0;
    }
    D[1]=0;
    vis[1]=1;
    double sum=0;
    for(int i=2;i<=n;++i){
        D[i]=min(D[i],cost[1][i]-ans*len[1][i]);
    }

    for(int i=1;i<=n-1;++i){
        double minn=1e18;
        int kep=i;
        for(int j=1;j<=n;++j){
            if(vis[j]==0&&D[j]<minn){
                minn=D[j];
                kep=j;//最小的节点编号
            }
        }

        sum+=minn;
        vis[kep]=1;
        for(int j=1;j<=n;++j){
            if(vis[j]==0&&D[j]>cost[kep][j]-ans*len[kep][j]){
                D[j]=cost[kep][j]-ans*len[kep][j];//？？？双向图交换位置就T
            }
        }
    }
    if(sum<=0)return 1;
    else return 0;
}
int main(){
    while(scanf("%lld",&n)!=EOF){
        if(n==0)break;

        rep(i,1,n){
            scanf("%lf%lf%lf",&q1[i].x,&q1[i].y,&q1[i].high);
        }
        rep(i,1,n){
            rep(j,1,n){
                
                    double d=length(q1[i],q1[j]);
                    double h=high(q1[i],q1[j]);
                    len[i][j]=len[j][i]=d;
                    cost[i][j]=cost[j][i]=h;
                
            }
        }
        double l=0;
        double r=100;
        double ans=0;
        for(int i=1;i<=50;++i){
            double mid=(l+r)/2.0;
            if(check(mid)){
                ans=mid;
                r=mid;
            }
            else {
                l=mid;
            }
        }
        printf("%.3f\n",ans);
    }
    return 0;
}

POJ2728 Desert King（最优比率生成树）

原文：https://www.cnblogs.com/quuns/p/14399004.html