程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj2728 Desert King，最優比例生成樹

poj2728 Desert King，最優比例生成樹

編輯：C++入門知識

poj2728 Desert King，最優比例生成樹

題意：有n個村莊，村莊在不同坐標和海拔，現在要對所有村莊供水，只要兩個村莊之間有一條路即可，
建造水管距離為坐標之間的歐幾裡德距離（好象是叫歐幾裡德距離吧），費用為海拔之差
現在要求方案使得費用與距離的比值最小
很顯然，這個題目是要求一棵最優比率生成樹，

0-1分數規劃，0-1分數規劃是分數規劃的一種特殊情況，分數規劃適用於求解最優化問題的，對於求最大的對應解，該理論也有效
這是從網上找到的具體的最優比率生成樹的方法的講解
////////////////////
概念
有帶權圖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). 我們可以興高采烈地把z(l)看做以d為邊權的最大生成樹的總權值.
然後明確兩個性質:
　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最大.
到了這個地步, 七竅全已打通, 喜歡二分的上二分, 喜歡Dinkelbach的就Dinkelbach.

復雜度
時間 O( O(MST) * log max(r) )
空間 O( O(MST) )
/////////////////////////////
關於分數規劃的學習我找到了一篇論文，裡面有講分數規劃，特別詳細
算法合集之《最小割模型在信息學競賽中的應用》
黑書上說求最小生成樹有O（n）的方法，沒去找

迭代+prim

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define for0(a,b) for(a=0;a=b;--i)
using namespace std;
typedef long long ll;
const int maxn = 1000 + 5;
const int maxm = 100005;
const int INF = 1e9;

double x[maxn], y[maxn], z[maxn];
double cost[maxn][maxn], dist[maxn][maxn];
int n;
double Dist(int i, int j)
{
    return sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
}

void init()
{
    int i, j;
    for1(i,n) scanf("%lf%lf%lf", &x[i], &y[i], &z[i]);
    for1(i,n) foru(j,i+1,n){
        dist[i][j] = dist[j][i] = Dist(i, j);
        cost[i][j] = cost[j][i] = fabs(z[i] - z[j]);
    }
}

    int vis[maxn], pre[maxn];
    double dis[maxn];
double prim(double p)
{
    int i, j;
    memset(vis, 0, sizeof vis ); vis[1] = 1;
    foru(i,2,n) {
        dis[i] = cost[1][i]-dist[1][i]*p;
        pre[i] = 1;
    }

    double Cost = 0, Len = 0;
    for0(i,n-1){
        double Mincost = INF;
        int k = -1;
        for1(j,n){
            if(!vis[j] && dis[j]tmp){
                dis[j] = tmp;
                pre[j] = k;
            }
        }
    }
    return Cost / Len;
}

void solve()
{
    //牛頓迭代
    double x0=0, x=0;
    while(true){
        x = prim(x0);
        if(fabs(x-x0)<1e-4) break;
        x0 = x;
    }
    printf("%.3f\n", x);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.cpp","r",stdin);
    freopen("out.cpp", "w", stdout);
#endif // ONLINE_JUDGE
    int i, j;
    while(~scanf("%d", &n))
    {
        if(n==0) break;
        init();
        solve();
    }
    return 0;
}