POJ 2728 Desert King

01分数规划之最优比例生成树……
这道题，好坑……

一开始WA了，然后找了一个博客，WA，照着敲，WA，再照着敲，WA，索性复制再改，WA，最后复制粘贴，他的也WA了。md

感觉我写题的时候很容易石乐志，然后就很难过题……
好几场比赛都验证了……

题意：
给你一张图上的所有点，由所有点得出每条边的两个权值，欧式距离与高度差。
要你和找出一个生成树，使得 高度差的和比上欧式距离和最小。

思路：
最优比例生成树的经典题。其实只要掌握了01分数规划的思想，你就照着prime敲就好了。
我这里用了迭代法，感觉迭代法更套路一些……而且速度比较快。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const double inf = 0x3f3f3f3f3f;
const double eps = 1e-6;
const int maxn = 1e3 + 10;

int n;
double dist[maxn][maxn];
int x[maxn], y[maxn], h[maxn];
bool vis[maxn];
int pre[maxn];
double dis[maxn];

double prime(double L)
{
    double sc = 0, ss = 0;
    range(i, 1, n)
    {
        pre[i] = 1;
        dis[i] = abs(h[1] - h[i]) - dist[1][i] * L;
    }
    pre[1] = -1;
    range(i, 2, n)
    {
        double mi = inf;
        int v = -1;
        range(j, 1, n) if (pre[j] != -1 && dis[j] < mi)
        {
            v = j;
            mi = dis[j];
        }
        if (v != -1) {
            sc += abs(h[pre[v]] - h[v]);
            ss += dist[pre[v]][v];
            pre[v] = -1;
            range(j, 1, n)
            {
                double tmp = abs(h[v] - h[j]) - dist[v][j] * L;
                if (pre[j] != -1 && tmp < dis[j]) {
                    dis[j] = tmp;
                    pre[j] = v;
                }
            }
        }
    }
    return sc / ss;
}

inline double calc(int a, int b) { return (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]); }

int main()
{
    while (scanf("%d", &n) != EOF && n) {
        range(i, 1, n) scanf("%d %d %d", x + i, y + i, h + i);
        range(i, 1, n) range(j, i, n) dist[j][i] = dist[i][j] = sqrt(calc(i, j));
        double ans = 0, L;
        do {
            L = ans;
            ans = prime(L);
        } while (fabs(ans - L) >= eps);
        printf("%.3f\n", ans);
    }
    return 0;
}