@DATASOURCE 2015-09-04T14:24:12.000000Z 字数 4084 阅读 2255

最优比率生成树

图论 生成树

简述

引入：传说在2005年北京现场赛的赛场上，楼教主在5分钟搞定一题后第25分钟搞定了这个题，让所有人都以为这是一道水题，带坏了全场的节奏，200多次提交只有8个人过， 最终顺利夺冠。

我们设一个顶点数为n，边数为m的无环连通图G，其中 cost[i] 表示是第i条边花费的代价，benefit[i] 表示第i条边获得的收益，现要求这个图的一个生成树，使得这棵树的总花费与总收益的比值最小。这个问题就是解决最优比率生成树的问题。在实际问题当中，我们会经常遇到如修建道路要考虑收益和开销，使得代价比最小的问题。

算法

设 x[i] 等于 1 或 0 , 表示边 e[i] 是否属于生成树. 则我们所求的比率

r = \sum (b e n e f i t [i] * x [i]) / \sum (c o s t [i] * x [i]), 0 \leq i < m

$r = ∑(benefit[i] * x[i]) / ∑(cost[i] * x[i]), 0≤i<m$ 为了使 r 最大, 设计一个子问题---> 让

z = \sum (b e n e f i t [i] * x [i]) - r * \sum (c o s t [i] * x [i]) = \sum (d [i] * x [i]), 其 中 (d [i] = b e n e f i t [i] - l * c o s t [i])

$z = ∑(benefit[i] * x[i]) - r * ∑(cost[i] * x[i]) = ∑(d[i] * x[i]), 其中(d[i] = benefit[i] - l * cost[i])$ 并记为 z(r) .

然后明确两个性质 :
1. z单调递减
证明: 因为cost为正数, 所以z随l的减小而增大.
2. z( max(r) ) = 0
证明: 若
$z (m a x (r)) < 0$ $z( max(r) ) < 0$ 则 $\sum (b e n i f i t [i] * x [i]) - m a x (r) * \sum (c o s t [i] * x [i]) < 0$ $∑(benifit[i] * x[i]) - max(r) * ∑(cost[i] * x[i]) < 0$ 可化为 $m a x (r) < m a x (r)$ $max(r) < max(r)$ 矛盾;
若 $z (m a x (r)) > = 0$ $z( max(r) ) >= 0$ , 根据性质1, 当 z = 0 时r最大.

这样上面的问题就转化为了求 z(r) 的零点问题, 方法有以下两个:

A、迭代法：由上面的分析可知：
当 z(r) > 0 时，rate 值无效，而 rateNex 有效且z(rateNex) <= 0;
当 z(rate) < 0 时，rateNex < rate，又 z(rate) 为单调递减函数，故 0 >= z(rateNex) > z(rate)。
故迭代过程向 z(rate) == 0 收敛，又由有限节点的完全图其生成树只有有限个可知迭代次数必为有限值。

B、二分法：在定出一个搜索范围和精度之后(以[0,MAXRATE]为例)，我们就可以使用二分法进行搜索：对于当前的搜索区间[low,high]，mid = (low + high) / 2，根据 z(mid) 的值及 z(rate) 的增减性，对搜索区间进行更新：
从而在经过有限次搜索之后便能找到所求比率。

例题 POJ 2728

题意：有n个村庄要连在一起，村与村之间的长度为他们之间的水平距离，连在一起的花费是两村的高度差。现求所花费和与长度和之比最小

输入: n 和 n 个村庄的三维坐标

输出: 花费和与长度和的最小比值

// 二分
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define ABS(x) ((x) > 0 ? (x) : (-(x)))
using namespace std;
const double eps = 1e-4;
const int MAXN = 1010;
const int MAX_INT = (1 << 29);
struct Point{
    double x, y, h;
    double CalDis(const Point &a){
        return sqrt((a.x - x) * (a.x - x) + (a.y - y) * (a.y - y));
    }
    double CalHig(const Point &a){
        return ABS(h - a.h);
    }
};
Point a[MAXN];
int n;
double mp[MAXN][MAXN];
double dis[MAXN][MAXN]; 
double cost[MAXN][MAXN];
bool vis[MAXN];
double dist[MAXN];
double prim(int s){
    memset(vis, false, sizeof(vis));
    fill(dist, dist + MAXN, MAX_INT);
    vis[s] = true;
    dist[s] = 0;
    double mi;
    int mip = s;
    double ans = 0;
    for(int i = 0; i < n; i++)
        dist[i] = mp[s][i];
    for(int i = 1; i < n; i++){
        mi = MAX_INT;
        for(int j = 0; j < n; j++)
            if(!vis[j] && mi > dist[j]) mi = dist[j], mip = j;
        ans += mi;
        vis[mip] = true;
        for(int j = 0; j < n; j++)
            if(!vis[j] && dist[j] > mp[mip][j])
                dist[j] = mp[mip][j];
    }
    return ans;
}
bool check(double mid){
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            mp[i][j] = mp[j][i] = cost[i][j] - mid * dis[i][j];
        }
    }
    double mst = prim(0);
    if(mst > eps) return true;
    else return false;
}
double solve(){
    double l = 0.0, r = 100.0, mid;
    while(r - l > eps){
        mid = (l + r) / 2.0;
        if(check(mid)) l = mid;
        else r = mid;
    }
    return l;
}
int main(){
    while(scanf("%d", &n) != EOF){
        if(!n) break;
        for(int i = 0; i < n; i++)
            scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].h);
        fill(dis[0], dis[MAXN], MAX_INT);
        for(int i = 0; i < n; i++)
            for(int j = i + 1; j < n; j++){
                dis[i][j] = dis[j][i] = a[i].CalDis(a[j]);
                cost[i][j] = cost[j][i] = a[i].CalHig(a[j]);
            }
        double ans = solve();
        printf("%.3f\n", ans);
    }
    return 0;
}

// 牛顿迭代法
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define ABS(x) ((x) > 0 ? (x) : (-(x)))
using namespace std;
const double eps = 1e-5;
const int MAXN = 1010;
const double MAX_INT = (1 << 29) / 1.0;
struct Point{
    double x, y, h;
    double CalDis(const Point &a){
        return sqrt((a.x - x) * (a.x - x) + (a.y - y) * (a.y - y));
    }
    double CalHig(const Point &a){
        return ABS(h - a.h);
    }
};
int n;
int pre[MAXN];
Point a[MAXN];
double mp[MAXN][MAXN];
double dis[MAXN][MAXN]; 
double cost[MAXN][MAXN];
bool vis[MAXN];
double dist[MAXN];
double prim(){
    int s = 0;
    memset(vis, false, sizeof(vis));
    memset(pre, 0, sizeof(pre));
    fill(dist, dist + MAXN, MAX_INT);
    vis[s] = true;
    dist[s] = 0.0;
    int mip = s;
    double mi = 0.0, dissum = 0.0, costsum = 0.0;
    for(int i = 1; i < n; i++){
        for(int j = 0; j < n; j++)
            if(!vis[j] && dist[j] > mp[mip][j]){
                dist[j] = mp[mip][j];
                pre[j] = mip;
            }
        mi = MAX_INT;
        for(int j = 0; j < n; j++)
            if(!vis[j] && mi > dist[j]) mi = dist[j], mip = j;
        vis[mip] = true;
        dissum += dis[mip][pre[mip]];
        costsum += cost[mip][pre[mip]];
    }
    return costsum / dissum;
}
inline void change(double mid){
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
            mp[i][j] = mp[j][i] = cost[i][j] - mid * dis[i][j];
}
double solve(){
    double last = 0.0, cur = -1.0;
    while(ABS(cur - last) > eps){
        last = cur;
        change(last);
        cur = prim();
    }
    return last;
}
int main(){
    while(scanf("%d", &n) != EOF){
        if(!n) break;
        for(int i = 0; i < n; i++)
            scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].h);
        for(int i = 0; i < n; i++)
            for(int j = i + 1; j < n; j++){
                dis[i][j] = dis[j][i] = a[i].CalDis(a[j]);
                cost[i][j] = cost[j][i] = a[i].CalHig(a[j]);
            }
        for(int i = 0; i < n; i++)
            dis[i][i] = cost[i][i] = 0.0;
        double ans = solve();
        printf("%.3f\n", ans);
    }
    return 0;
}

最优比率生成树

简述

算法

例题 POJ 2728

内容目录