POJ2728 Desert King 最优比率生成树

题目 http://poj.org/problem?id=2728

关键词：0/1分数规划，参数搜索，二分法，dinkelbach

参考资料：http://hi.baidu.com/zzningxp/item/28aa46e0fd86bdc2bbf37d03

               http://hi.baidu.com/zheng6822/item/b31fbe9d5ae17536336eeb8f

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
#define N 1010
#define INF 1e15
#define eps 1e-10
using namespace std;
double X[N],Y[N],Z[N];
double cost[N][N];
double lowcost[N];
int closest[N];int vis[N];
int n;double r;
double disc(int i,int j)
{
    return fabs(Z[i]-Z[j]);
}
double disd(int i,int j)
{
    return sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]));
}
double prim(double r)
{
    double sumc=0;double sumd=0;
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    {
        if(i==j)
        cost[i][j]=INF;
        else
        cost[i][j]=disc(i,j)-r*disd(i,j);
    }
    for(int i=0;i<n;i++)
    {
        lowcost[i]=cost[0][i];
        vis[i]=0;
        closest[i]=0;
    }
    closest[0]=0;
    vis[0]=1;
    int k;
    for(int i=0;i<n;i++)
    {
        double tmp=INF;
        for(int j=0;j<n;j++)
        if(!vis[j]&&tmp>lowcost[j])
        {
            k=j;
            tmp=lowcost[j];
        }
        vis[k]=1;
        for(int j=0;j<n;j++)
        if(!vis[j]&&lowcost[j]>cost[k][j])
        {
            lowcost[j]=cost[k][j];
            closest[j]=k;
        }
    }
    for(int i=0;i<n;i++)
    {
        sumc+=disc(i,closest[i]);
        sumd+=disd(i,closest[i]);
    }
    return sumc/sumd;
}
int main()
{
    while(scanf("%d",&n)!=EOF&&n)
    {
        for(int i=0;i<n;i++)
        cin>>X[i]>>Y[i]>>Z[i];
        double r1=0,r2=0;
        while(1)
        {
            r2=prim(r1);
            if(fabs(r1-r2)<=eps)
            break;
            r1=r2;
        }
        printf("%.3f
",r1);
    }
    return 0;
}

 主要算法部分的分析

double prim(double r)
{
    /*根据题目要求和算法得到由新的权值组成的图，并且写出邻接矩阵*/
    double sumc=0;double sumd=0;
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    {
        if(i==j)
        cost[i][j]=INF;
        else
        cost[i][j]=disc(i,j)-r*disd(i,j);
    }
    /*初始化*/
    for(int i=0;i<n;i++)
    {
        lowcost[i]=cost[0][i];  
        vis[i]=0;    /*判断该点是否已经在集合内*/
        closest[i]=0;  /*邻接点*/
    }
    /*将第一个点加入集合*/
    closest[0]=0;
    vis[0]=1;
    int k;
    for(int i=0;i<n;i++)
    {
        double tmp=INF;
        /*通过一次循环找到与第一个点距离最短的点*/
        for(int j=0;j<n;j++)
        if(!vis[j]&&lowcosat[j]<tmp)
        {
            k=j;
            tmp=lowcost[j];
        }
        /*将该点加入集合中*/
        vis[k]=1;
        /*这一步是更新其他的点到集合中的点的距离，closest是用来记录该点的前驱的点的数组，lowcost是用来记录其他点到MST的最短距离的数组，注意是到树上任意一点而不是其中某点*/
        for(int j=0;j<n;j++)
        if(!vis[j]&&lowcost[j]>cost[j][k])
        {
            lowcost[j]=cost[j][k];
            closest[j]=k;
        }
    }
    /*返回参数，用于迭代*/
    for(int i=0;i<n;i++)
    {
        sumc+=disc(i,closest[i]);
        sumd+=disd(i,closest[i]);
    }
    return sumc/sumd;    
}