最优比率生成树

最优比率生成树题意与最小生成树基本相同，但由单一边权的最小值转化为第一边权的总和与第二边权的总和比值的最小值，这导致算法发生巨大变化，以致于需要采用二分的方法，并进行一系列复杂的判定……（好吧，是我看来）
对于给定的有向图，要求求出一颗子树G，使其各边收益总和与花费的总和比值尽可能小，即Σ(benifit[i])/Σ(cost[i]) i∈G，我们可以二分答案λ的上下界[0,∞)（事实上上界取2^就好了），当λ为最优解时f(λ)=Σ(benifit[i])-λ*Σ(cost[i])=Σ(d[i])=0 i∈G（d[i]=benifit[i]-λ*cost[i]）

接着我们很容易得知，f(x)是单调递减的，因此，若f(λ)≠0，便可缩小搜索范围，二分复杂度是log(max)。至于求f(λ)的值，明显要使其尽可能小，又要满足构成树，以d[i]为边权的最小生成树便可以满足要求。
我们理一下代码思路：
①按上下界二分λ，开始，判定；
②更新单一边权d[i]=benifit[i]-λ*cost[i]；
③求出此时的最小生成树；
④若f(x)=0，则λ为所求解，否则继续循环；
代码如下：

#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; 
        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;
}

此外，采用Dinkelbach进行迭代，复杂度更低一些，苣蒻在这里就不详述了，代码如下：

#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;
}

最优比率生成树

推荐阅读