程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [POJ 2728] 最優比例生成樹

[POJ 2728] 最優比例生成樹

編輯：C++入門知識

概念

有帶權圖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

為了使 r 最大, 設計一個子問題---> 讓 z = ∑(benifit[i] * x[i]) - l * ∑(cost[i] * x[i]) = ∑(d[i] * x[i]) 最大 (d[i] = benifit[i] - l * cost[i]) , 並記為z(l).

然後明確兩個性質:

　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最大.

/*
ID: [email protected]
PROG:
LANG: C++
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define maxn 1010
#define INF (1<<30)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define For(i, n) for (int i = 0; i < n; i++)
#define eps (1e-5)
typedef long long ll;


//二分法 復雜度較高
using namespace std;
int n, vis[maxn], pre[maxn];
struct node {
    int x, y, z;
} p[maxn];
double edge[maxn][maxn];
void init() {
    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 = i; j <= n; j++)
            edge[i][j] = edge[j][i] = sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y));
    }
}
double dis[maxn];
double prim(double l) {
    mem(vis, 0);
    for (int i = 2; i <= n; i++) {
        dis[i] = abs(p[i].z - p[1].z) - edge[1][i] * l;
        pre[i] = 1;
    }
    vis[1] = 1;
    double cost = 0;
    for (int i = 1; i < n; i++) {
        int k = -1;
        double mn = INF;
        for (int j = 1; j <= n; j++) if (!vis[j] && dis[j] < mn) {
                mn = dis[j];
                k = j;
            }
        if (k != -1) {
            vis[k] = 1;
            cost += dis[k];
            for (int j = 1; j <= n; j++) if (!vis[j]) {
                    double val = abs(p[k].z - p[j].z) - edge[k][j] * l;
                    if (dis[j] > val) {
                        dis[j] = val;
                        pre[j] = k;
                    }
                }
        }
    }
    return cost;
}
void binary() {
    double low = 0, high = 100.0, mid;
    while(high - low > eps) {
        mid = (high + low) / 2;
        if (prim(mid) >= 0) low = mid;
        else high = mid;
    }
    printf("%.3f\n", mid);
}
int main () {
    while(scanf("%d", &n) != EOF) {
        if (!n) break;
        init();
        binary();
    }
    return 0;
}


//迭代法 
using namespace std;
int n, vis[maxn], pre[maxn];
struct node {
    int x, y, z;
} p[maxn];
double edge[maxn][maxn];
void init() {
    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 = i; j <= n; j++)
            edge[i][j] = edge[j][i] = sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y));
    }
}
double dis[maxn];
double prim(double l) {
    mem(vis, 0);
    for (int i = 2; i <= n; i++) {
        dis[i] = abs(p[i].z - p[1].z) - edge[1][i] * l;
        pre[i] = 1;
    }
    vis[1] = 1;
    double cost = 0, len = 0;
    for (int i = 1; i < n; i++) {
        int k = -1;
        double mn = INF;
        for (int j = 1; j <= n; j++) if (!vis[j] && dis[j] < mn) {
                mn = dis[j];
                k = j;
            }
        if (k != -1) {
            vis[k] = 1;
            cost += abs(p[k].z - p[pre[k]].z);
            len += edge[k][pre[k]];
            for (int j = 1; j <= n; j++) if (!vis[j]) {
                    double val = abs(p[k].z - p[j].z) - edge[k][j] * l;
                    if (dis[j] > val) {
                        dis[j] = val;
                        pre[j] = k;
                    }
                }
        }
    }
    return cost / len;
}
void iter() {
    double a = 0, b;
    while(1) {
        b = prim(a);
        if(fabs(a - b) < eps) break;
        a = b;
    }
    printf("%.3f\n", b);
}
int main () {
    while(scanf("%d", &n) != EOF) {
        if (!n) break;
        init();
        iter();
    }
    return 0;
}