POJ 2728：Desert King（最优比率生成树）

http://poj.org/problem?id=2728

题意：有n个点，有三个属性代表每个点在平面上的位置，和它的高度。点与点之间有一个花费：两点的高度差；还有一个长度：两点的距离。现在要让你在这n个点里面弄一个生成树，使得∑cost / ∑dis 最小，问最小的比率是多少。

思路：求得的比率R = ∑(cost[i] * x[i]) / ∑(dis[i] * x[i])，x[i]为1代表选这个点，转化一下，就是要minimize（R）。

设F（L） = ∑(cost[i] * x[i]) - ∑(dis[i] * L * x[i])  = ∑(cost[i] - dis[i] * L) * x[i] = ∑D[i] * x[i] （D[i] = cost[i] - L * dis[i]）。

我们要使得L越小越好，那么L越小，D[i]就会越大，因此我们要求得的是最小能达到的D[i]使得这个方程成立，这样的边界时候的L才是最小的。

那么我们可以先随便假设一个L，然后通过使用最小生成树（把上面的D[i]当做边权），判断当前的L还能够更优，当迭代到一定次数之后，就可以得出正确答案了（当然也可以二分搜索）。

具体写的很详细的：http://blog.csdn.net/hhaile/article/details/8883652

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define N 10010
const double eps = 1e-7;
const double INF = 1000000000;
struct node {
    double x, y, z;
} p[N];
double low[N], cost[N][N], dis[N][N];
int vis[N], pre[N], n;

double sqr(double x) { return x * x; }

double Prim(double k) {
    double fz = 0, fm = 0, mi; int index;
    for(int i = 1; i <= n; i++) low[i] = cost[1][i] - dis[1][i] * k, vis[i] = 0, pre[i] = 1;
    vis[1] = 1; // 记得
    for(int i = 1; i < n; i++) {
        mi = INF, index = -1;
        for(int j = 1; j <= n; j++)
            if(!vis[j] && mi > low[j]) mi = low[index = j];
        if(index == -1) break;
        vis[index] = 1;
        fz += cost[index][pre[index]]; fm += dis[index][pre[index]];
        for(int j = 1; j <= n; j++)
            if(!vis[j] && (cost[index][j] - dis[index][j] * k) < low[j])
                low[j] = cost[index][j] - dis[index][j] * k, pre[j] = index;
    }
    return fz / fm;
}

double solve() {
    double ans = 0, tmp = 1;
    while(1) {
        tmp = Prim(ans);
        if(fabs(tmp - ans) <= eps) break;
        ans = tmp;
    }
    return tmp;
}

int main() {
    while(~scanf("%d", &n), n) {
        for(int i = 1; i <= n; i++) scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z);
        for(int i = 1; i <= n; i++) {
            for(int j = i + 1; j <= n; j++) {
                cost[i][j] = cost[j][i] = fabs(p[i].z - p[j].z);
                dis[i][j] = dis[j][i] = sqrt(sqr(p[i].x - p[j].x) + sqr(p[i].y - p[j].y));
            }
        }
        printf("%.3f
", solve());
    }
    return 0;
}