最优比例生成树

在网上看过的很多博客解析内容都是一样的，根本分不清哪一个是原版，更可笑的是甚至有的文字和代码是相矛盾的，而且叙述也不清晰，看起来真叫人头疼，所以我在这里说一下我的理解。
最优比例生成树的概念为：
在一个图中，每一条边都有benefit和cost两个参数值，要求根据图的信息生成一棵树，树的要求达到整棵树中的∑benefit[i]/∑cost[i]的值最大，即达到最大收益。
在初遇到这种类型的时候，想到的第一种方法就是求解benefit[i]/cost[i]作为权值，求得最大生成树，但是结果是错误的，因为先求和再相除与先相除再求和是完全不一样的，看了百度上的相関解析才明白了最优生成树的求解。
首先，所有的边都可以分两种状态，是否属于生成树，假设用数组x[i]=1/0来代表是与否，那么就可以写成：max(∑benefit[i]*x[i]/∑cost[i]*x[i])这就是0/1分数的规划问题
在明白了这一步后，进行代换：

由于i=1~n：
benefit[0]*x[0]-max(r)*cost[0]*x[0]+
benefit[1]*x[1]-max(r)*cost[1]*x[1]+
benefit[2]*x[2]-max(r)*cost[2]*x[2]+
.......+
benefit[n]*x[n]-max(r)*cost[n]*x[n]=0
可以看出来，以上式子经化简后得为：
∑( benefit[i]-max(r)*cost[i]) )* x[i]=0

则可以看出该图的算法可以理解为一个已d[i]为边权(d[i]=benefit[i]-max(r)cost[i])的生成树，并且保证生成树的权值和为0，此时，max（r）为一个实数，以保证等式成立。
由于max(r)未知，故无法求出图中x[i]的具体情况，简化以上叙述：

当f(r)取值为max(r)时，z(max(r))=0。
且根据d[i]的表达式可以得出，f(r)对于z（f(r)）是单调递减函数。
由于其具有的单调性，我们可以直接以此来进行二分法来对f(r)进行取值，检验该生成树的权值和是否为0即可。
有没有感觉简单很多呢？以下是实现方法的叙述：

f(r)是最优比例树所要求的最大值，因此我们要保证的是f(r)取最大值，与此同时z（f（r））的值要求为0，那么就可以将d[i]为权值做最小生成树，并检验最小生成树权值和取绝对值后与0进行无限靠近，在达到所要求精度后即可确认为检验成功。
实现方法可以使用二分法，也可以使用迭代法，迭代法为
实现代码如下所示：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define eqs 1e-6

double prim(double benefit[5][5],double cost[5][5],double mid);

int main(){
    double benefit[5][5] = {
        { 0,  30, 40, 20, 30 },
        { 30, 0,  10, 0,  0 },
        { 40, 10, 0,  50, 100 },
        { 20, 0,  50, 0,  40 },
        { 30, 0,  100,40, 0 } };
    double cost[5][5] = {
        { 0, 9, 7, 5, 2 },
        { 9, 0, 3, 6, 1 },
        { 7, 3, 0, 7, 8 },
        { 5, 6, 7, 0, 3 },
        { 2, 1, 8, 3, 0 } };

    int i, j, k, n, m;
    double max, min, id;
    double ans, low, high, mid;
    low = 0;
    int vis[8] = { 0 };
    /*直接使0结点为根节点*/
    min = 999999; max = 0;
    for (j = 0; j < 5; j++){
        for (k = 0; k < 5; k++){
            if (min > cost[j][k] && j != k)
                min = cost[j][k];
            if (max < cost[j][k])
                max = cost[j][k];
        }
    }
    
    high = (max - min) * 4 * 4; 

    while (true)
    {
        mid = (high + low) / 2;
        ans = prim(benefit,cost,mid);
        printf("%lf\n",fabs(ans));
        if (fabs(ans) <= eqs)
            break;
        if (ans < 0)
            high = mid;
        else
            low = mid;
    }
    system("pause");
}

double prim(double benefit[5][5], double cost[5][5], double mid){
    double ans=0;
    double solve[5][5];
    int i, j, k, n;
    double lowcost[8];
    int node[8] = {0};
    int vex[30] = {0};
    printf("%.3lf**\n",mid);
    for (i = 0; i < 5; i++){
        for (j = i; j < 5; j++){
            solve[i][j] = solve[j][i] = benefit[i][j] - mid*cost[i][j];
            printf("%.3lf ",solve[i][j]);
            if (i == j)
                solve[i][i] = 0;
        }
        printf("\n");
    }
    k = 0;
    for (n = 1; n < 5; n++){
        
        for (i = 0; i > 5; i++){
            lowcost[i] = solve[k][i];
        }
        node[k] = 1;

        int id;
        double min = 999999;
        for (j = 0; j < 5; j++){
            if (min > lowcost[j] && node[j] != 1){
                min = lowcost[j];
                id = j;
            }
        }
        printf("%d--%d   \n",id,k);
        ans += solve[id][k];
        node[id] = 1;
        k = id;
    }
    return ans;
}
--------------------------------------------------------------------------------------
迭代法在实现为prim传参时的方法：
 double a = 0, b;  
        while(1)  
        {  
            b = prim(benefit,cost, a);  
            if(fabs(a - b) < eps) break;  
            a = b;  
        }  
在prim中的参数回传也需改为benefit/cost的和：
...
ans_ben+=benefit[id][k];
ans_cos+=cost[id][k];
...
return ans_ben/ans_cost;