算法竞赛进阶指南368页，最小生成树，0/1分数规划
题目意思：
n个点，每个点以平面坐标 (x, y) 表示， 其海拔高度是 z。 点与点之间的距离就是 (x1, y1) 与 (x2, y2) 的
平面距离 （这里用数组 a[MaxN][MaxN] 来存）。
点与点之间的高度差值的绝对值，叫做成本（这里用数组 b[MaxN][MaxN] 来存）。
题目要求，找到一个图的生成树，使得这棵树 总的成本 sum{成本} / sum{距离} 最大。
本题要点：
1、 二分法，构造一个新的无向图， 边的权值 是 a[i][j] - mid * b[i][j] 。
然后二分 mid, 直到找到最小的 mid， 使得 这棵树的最大生成树 的总边权为0.
2、稠密图，套用 prim 算法，得到 特定 mid 值下的图中的最大生成树。
d[k] 表示 k点到这棵树的距离。 d[1] + d[2] + … + d[n] 就是这棵树的总的权值。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int MaxN = 1010, INF = 0x3f3f3f3f;
int n;
double eps = 1e-6, a[MaxN][MaxN], b[MaxN][MaxN];
double d[MaxN];
bool vis[MaxN];struct node
{
int x, y, z;
}village[MaxN];bool prim(double mid)
{
memset(vis, false, sizeof vis);for(int i = 0; i <= n; ++i)d[i] = INF;d[1] = 0;double ans = 0;for(int i = 1; i < n; ++i) {
int x = 0;for(int j = 1; j <= n; ++j){
if(!vis[j] && (0 == x || d[j] < d[x]))x = j;}if(!x) break;vis[x] = 1;for(int y = 1; y <= n; ++y){
if(!vis[y]){
if(d[y] > a[x][y] - mid * b[x][y]){
d[y] = a[x][y] - mid * b[x][y];}}}}for(int i = 1; i <= n; ++i)ans += d[i];return ans >= 0;
}void solve()
{
double x1, y1, r = 0;for(int i = 1; i <= n; ++i){
for(int j = i + 1; j <= n; ++j){
a[i][j] = a[j][i] = abs(village[i].z - village[j].z);r += a[i][j];x1 = village[i].x - village[j].x, y1 = village[i].y - village[j].y;b[i][j] = b[j][i] = sqrt(x1 * x1 + y1 * y1); }}double l = 0, mid = (l + r) / 2;while(r - l > eps){
mid = (l + r) / 2; if(prim(mid)){
l = mid;}else{
r = mid;}}printf("%.3f\n", l);
}int main()
{
while(scanf("%d", &n) != EOF && n){
for(int i = 1; i <= n; ++i){
scanf("%d%d%d", &village[i].x, &village[i].y, &village[i].z);}solve();}return 0;
}/* 4 0 0 0 0 1 1 1 1 2 1 0 3 0 *//* 1.000 */