POJ 2728 最优比率生成树 01分数规划问题

网上有一些很数学的证明方法，表示看的挺晕，自己理解了一下后，发表下自己的看法，如果有错误，再进行修改

其实原题就是求 MIN（ ∑CiXi / ∑DiXi ）Xi∈{0，1} ，对每个生成树，设其比率r=∑CiXi / ∑DiXi ，可得∑CiXi - ∑DiXi * r=0（条件1）

那么对于所有的生成树，显然∑CiXi - ∑DiXi * min(r) >= 0，当 ∑CiXi / ∑DiXi = min(r)时，等号成立。而我们现在不知道min(r)是多少，只好进行枚举，对每个枚举的r ,构建新的权值（Ci-Di*r），然后求最小生成树， 为什么求最小呢？ 我的理解就是这是为了寻找使得生成树的总权值为0的可能性，因为只有当其等于0 的时候，才满足了条件1 这个条件， 说明这个r是可行的，并且如果r枚举到值为min(r)时，其最小生成树的的总权值必然恰好等于0，但是如果不能等于0， 比如大于0， 显然是对该r值，所有的生成树上无论如何也满足不了条件1，说明r值就是偏小了。同理如果小于0，r值是偏大的,说明可能存在某些生成树使得满足条件1，而我们的目标是在满足条件1的情况下使得r最小。

根据这个我们可以发现，实际上r的值是可以进行二分查找的。 而也有人给出了更为高效的迭代方法。

代码贴上：

首先是二分法

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define MAXN 1005
#define INF 1000000000
#define eps 1e-7
using namespace std;
int n;
double Edge[MAXN][MAXN], lowcost[MAXN];
int nearvex[MAXN];
struct Point
{
    int x, y, z;
}p[MAXN];
double cal(int a, int b)
{
    return sqrt(1.0 * (p[a].x - p[b].x) * (p[a].x - p[b].x) + 1.0 * (p[a].y - p[b].y) * (p[a].y - p[b].y));
}
double prim(int src, double l)
{
    double cost = 0, len = 0;
    double sum = 0;
    for(int i = 1; i <= n; i++)
    {
        nearvex[i] = src;
        lowcost[i] = abs(p[src].z - p[i].z) - Edge[src][i] * l;
    }
    nearvex[src] = -1;
    for(int i = 1; i < n; i++)
    {
        double mi = INF;
        int v = -1;
        for(int j = 1; j <= n; j++)
            if(nearvex[j] != -1 && lowcost[j] < mi)
            {
                v = j;
                mi = lowcost[j];
            }
        if(v != -1)
        {
            cost += abs(p[nearvex[v]].z - p[v].z);
            len += Edge[nearvex[v]][v];
            nearvex[v] = -1;
            sum += lowcost[v];
            for(int j = 1; j <= n; j++)
            {
                double tmp = abs(p[v].z - p[j].z) - Edge[v][j] * l;
                if(nearvex[j] != -1 && tmp < lowcost[j])
                {
                    lowcost[j] = tmp;
                    nearvex[j] = v;
                }
            }
        }
    }
    return sum;
}
int main()
{
    while(scanf("%d", &n) != EOF && n)
    {
        for(int i = 1; i <= n; i++)
            scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                Edge[i][j] = cal(i, j);
        double low = 0, high = 10.0;             //其实二分20多次已经很足够了
        double l = 0.0, r = 100.0, mid;
        while(r - l > eps)
        {
            mid = (l + r) / 2;
            if(prim(1, mid) >= 0) l = mid;
            else r = mid;
        }
        printf("%.3f\n", r);
    }
    return 0;
}

然后是迭代，注意跟二分法不同的就是prim函数的返回值不同

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define MAXN 1005
#define INF 1000000000
#define eps 1e-7
using namespace std;
int n;
double Edge[MAXN][MAXN], lowcost[MAXN];
int nearvex[MAXN];
struct Point
{
    int x, y, z;
}p[MAXN];
double cal(int a, int b)
{
    return sqrt(1.0 * (p[a].x - p[b].x) * (p[a].x - p[b].x) + 1.0 * (p[a].y - p[b].y) * (p[a].y - p[b].y));
}
double prim(int src, double l)
{
    double cost = 0, len = 0;
    for(int i = 1; i <= n; i++)
    {
        nearvex[i] = src;
        lowcost[i] = abs(p[src].z - p[i].z) - Edge[src][i] * l;
    }
    nearvex[src] = -1;
    for(int i = 1; i < n; i++)
    {
        double mi = INF;
        int v = -1;
        for(int j = 1; j <= n; j++)
            if(nearvex[j] != -1 && lowcost[j] < mi)
            {
                v = j;
                mi = lowcost[j];
            }
        if(v != -1)
        {
            cost += abs(p[nearvex[v]].z - p[v].z);
            len += Edge[nearvex[v]][v];
            nearvex[v] = -1;
            for(int j = 1; j <= n; j++)
            {
                double tmp = abs(p[v].z - p[j].z) - Edge[v][j] * l;
                if(nearvex[j] != -1 && tmp < lowcost[j])
                {
                    lowcost[j] = tmp;
                    nearvex[j] = v;
                }
            }
        }
    }
    return cost / len;
}
int main()
{
    while(scanf("%d", &n) != EOF && n)
    {
        for(int i = 1; i <= n; i++)
            scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                Edge[i][j] = cal(i, j);
        double a = 0, b;
        while(1)
        {
            b = prim(1, a);
            if(fabs(a - b) < eps) break;
            a = b;
        }
        printf("%.3f\n", b);
    }
    return 0;
}