poj2728-最小比率生成树/0-1分数规划/二分/迭代

题目意思：
有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[1] = 0; 
    memset(vis, 0, sizeof(vis)); 
    vis[1] = 1; 
    for (int i = 2; i <= n; ++ i) 
    { 
        dis[i] = cost[1][i] - dist[1][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; 
            } 
        } 
    } 
#if 0//0 for 二分， 1 for 迭代 
    return totalcost / totaldist; 
#else 
    return sum; 
#endif 
     
} 
int main() 
{ 
    while (scanf("%d", &n), n) 
    { 
        for (int i = 1; i <= n; ++ i) 
        { 
            scanf("%d%d%d", &x[i], &y[i], &z[i]); 
            for (int j = 1; j < i; ++ j) 
            { 
                double tmp = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]); 
                cost[i][j] = cost[j][i] = abs(z[i] - z[j]);//海拔 
                dist[i][j] = dist[j][i] = sqrt(tmp);//欧式距离 
            } 
        } 
        double a = 0; 
#if 0//1为迭代，0为二分 
        while (1)//迭代求最大值 
        { 
            double b = prim(a); 
            if (abs(a - b) < eps) 
            { 
                printf("%.3f/n", a); 
                break; 
            } 
            else 
                a = b; 
        } 
#else 
        double head = 0,tail = 100000.0; 
        while (tail - head > 1e-5) 
        { 
            double mid = (head + tail) / 2.0; 
            a = prim(mid); 
            if (a >= 0) 
            { 
                head = mid; 
            } 
            else 
                tail = mid; 
        } 
        printf("%.3f/n", tail); 
#endif 
    } 
    return 0; 
}