题目意思：
　　有n个村庄，村庄在不同坐标和海拔，现在要对所有村庄供水，只要两个村庄之间有一条路即可，建造水管距离为坐标之间的欧几里德距离，费用为海拔之差，现在要求方案使得费用与距离的比值最小，很显然，这个题目是要求一棵最优比率生成树。
　　0-1规划：
　　概念
　　有带权图G, 对于图中每条边e[i], 都有benifit[i]（收入）和cost[i]（花费）， 我们要求的是一棵生成树T, 它使得 ∑（benifit[i]） / ∑（cost[i]）， i∈T 最大（或最小）。这显然是一个具有现实意义的问题。
　　解法之一 0-1分数规划
　　设x[i]等于1或0, 表示边e[i]是否属于生成树。
　　则我们所求的比率 r = ∑（benifit[i] * x[i]） / ∑（cost[i] * x[i]）， 0≤i<m .
　　为了使 r 最大， 设计一个子问题---> 让 z = ∑（benifit[i] * x[i]） - l * ∑（cost[i] * x[i]） = ∑（d[i] * x[i]） 最大 （d[i] = benifit[i] - l * cost[i]） , 并记为z（l）。 我们可以兴高采烈地把z（l）看做以d为边权的最大生成树的总权值。
　　然后明确两个性质：
　　1. z单调递减
　　证明： 因为cost为正数， 所以z随l的减小而增大。
　　2. z（ max（r） ） = 0
　　证明： 若z（ max（r） ） < 0, ∑（benifit[i] * x[i]） - max（r） * ∑（cost[i] * x[i]） < 0, 可化为 max（r） < max（r）。 矛盾；
　　若z（ max（r） ） >= 0, 根据性质1, 当z = 0 时r最大。
　　代码：
　　if变量后面可以切换使用二分和迭代。if 0是二分，if 1是迭代，迭代300ms+,二分1400ms+
　　[cpp]
　　#include <stdio.h>
　　#include <stdlib.h>
　　#include <string.h>
　　#include <math.h>
　　#define nMax 1050
　　#define inf 0x7fffffff
　　static double eps = 1e-4;
　　int vis[nMax],x[nMax],y[nMax],z[nMax],pre[nMax];
　　double dis[nMax],cost[nMax][nMax],dist[nMax][nMax];
　　int n;
　　double prim（double x）//普利姆算法求最小生成树
　　{
　　double totalcost = 0, totaldist = 0;
　　double sum = 0.0;
　　for （int i = 1; i <= n; ++ i）
　　{
　　pre[i] = 1;
　　}
　　dis = 0;
　　memset（vis, 0, sizeof（vis））；
　　vis = 1;
　　for （int i = 2; i <= n; ++ i）
　　{
　　dis[i] = cost [i] - dist [i] * x;
　　}
　　int k;
　　for （int i = 2; i <= n; ++ i）
　　{
　　double minCost = inf;
　　for （int j = 2; j <= n; ++ j）
　　{
　　if （！vis[j] && dis[j] < minCost）
　　{
　　minCost = dis[j];
　　k = j;
　　}
　　}
　　vis[k] = 1;
　　sum += minCost;//for 二分
　　totalcost += cost[pre[k]][k];
　　totaldist += dist[pre[k]][k];
　　for （int j = 1; j <= n; ++ j）
　　{
　　if （！vis[j] && dis[j] > cost[k][j] - dist[k][j] * x）
　　{
　　dis[j] = cost[k][j] - dist[k][j] * x;
　　pre[j] = k;
　　}
　　}
　　}