POJ 2728 Desert King(最优比率生成树， 01分数规划)

题意：

给定n个村子的坐标（x,y）和高度z， 求出修n-1条路连通所有村子， 并且让 修路花费/修路长度 最少的值

两个村子修一条路， 修路花费 = abs(高度差), 修路长度 = 欧氏距离

分析：

01分数划分的题目， 构造出 d[i] = 修路花费 - L * 修路长度， 这个L值我们可以二分（这道题看数据范围的话二分上限其实挺大的， 但其实上限取到100就可以过）， 也可以用Dinkelbach迭代出来。

二分（1422ms）

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <cstring>

#include <cmath>

#define rep(i,a,b) for(int i = a; i < b;i++)

#define _rep(i,a,b) for(int i = a; i <= b;i++)

using namespace std;

const int maxn =  + ;

const double inf = 1e9 + ;

const double eps = 1e-;

int n;

double G[maxn][maxn];

double x[maxn], y[maxn], z[maxn];

inline double p2p_dis(double x1, double y1, double x2, double y2){

    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));

}

double prim(double L){

    double tree_dis = ;

    double dis[maxn];

    int vis[maxn];

    fill(dis, dis + maxn, inf);

    memset(vis,  ,sizeof(vis));

    dis[] = ;

    vis[] = ;

    for(int i = ; i < n; i++) dis[i] =  abs(z[] - z[i]) - L * G[][i];

    for(int times = ; times < n - ; times++){

        int picked = -;

        double min_dis = inf;

        for(int i = ; i < n; i++){

            if(!vis[i] && dis[i] < min_dis){

                min_dis = dis[i];

                picked = i;

            }

        }

        tree_dis += min_dis;

        vis[picked] = ;

        for(int i = ; i < n; i++)

            if(!vis[i])

                dis[i] = min(dis[i] , abs(z[picked] - z[i]) - L * G[picked][i]) ;

    }

    return tree_dis;

}

int main(){

//    freopen("1.txt","r", stdin);

    while(cin >> n && n){

        rep(i,,n) cin >> x[i] >> y[i] >> z[i];

        rep(i,,n) rep(j,i+,n) G[i][j] = G[j][i] = p2p_dis(x[i],y[i],x[j],y[j]);

        double l = , r = ;

        while(abs(r - l) > eps){

            double mid = (l + r) / ;

//            printf("%.3f\n", mid);

            if(prim(mid) >= ){

                l = mid;

            }else{

                r = mid;

            }

        }

        printf("%.3f\n", l);

    }

    return ;

}

Dinkelbach（204ms）

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <cstring>

#include <cmath>

#define rep(i,a,b) for(int i = a; i < b;i++)

#define _rep(i,a,b) for(int i = a; i <= b;i++)

using namespace std;

const int maxn =  + ;

const double inf = 1e9 + ;

const double eps = 1e-;

int n;

double G[maxn][maxn];

double x[maxn], y[maxn], z[maxn];

inline double p2p_dis(double x1, double y1, double x2, double y2){

    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));

}

double prim(double L){

    double ele = , deno = ; //分子分母

    double dis[maxn];

    int near[maxn]; //开一个数组记录每次选中是哪一条边

    int vis[maxn];

    fill(dis, dis + maxn, inf);

    memset(vis,  ,sizeof(vis));

    memset(near, -, sizeof(near));

    dis[] = ;

    vis[] = ;

    for(int i = ; i < n; i++) dis[i] =  abs(z[] - z[i]) - L * G[][i], near[i] = ; //每个点都是由0点更新的， 所以near都是0

    for(int times = ; times < n - ; times++){

        int picked = -;

        double min_dis = inf;

        for(int i = ; i < n; i++){

            if(!vis[i] && dis[i] < min_dis){

                min_dis = dis[i];

                picked = i;

            }

        }

        ele += abs(z[near[picked]] - z[picked]);//分子是选的路程

        deno += G[near[picked]][picked]; //分母是真实的花费

        vis[picked] = ;

        for(int i = ; i < n; i++)

            if(!vis[i] && dis[i] > abs(z[picked] - z[i]) - L * G[picked][i]){

                dis[i] = abs(z[picked] - z[i]) - L * G[picked][i];

                near[i] = picked;//如果通过picked点更新dis，那么该位置near就是picked

            }

    }

    return ele/deno; //注意返回的跟二分不一样， 应该返回当前L下真正题目的所求

}

int main(){

//    freopen("1.txt","r", stdin);

    while(cin >> n && n){

        rep(i,,n) cin >> x[i] >> y[i] >> z[i];

        rep(i,,n) rep(j,i+,n) G[i][j] = G[j][i] = p2p_dis(x[i],y[i],x[j],y[j]);

        double L, ans = ;

        while(){

            L = ans;

            ans = prim(L); //这是一个真实值， 不是含L的变式

            if(abs(ans - L)< eps) break;

        }

        printf("%.3f\n", ans);

    }

    return ;

}