POJ 2728 Desert King (最优比率生成树---01分数规划)

题目地址：POJ 2728

01分数规划的应用之一—最优比率生成树。

跟普通的01分数规划类似，只是这题的验证函数改成了最小生成树来验证。弱用的迭代法。

代码如下：

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
//#pragma comment(linker, "/STACK:1024000000")
const int mod=+;
const int INF=;
const double eqs=;
const int MAXN=+;
int bin[], n;
double p, q;
int find1(int x)
{
        return bin[x]==x?x:bin[x]=find1(bin[x]);
}
struct N
{
        int x, y, z;
}dian[];
struct node
{
        double w, dist, z;
        int u, v;
}edge[];
int cnt;
void add(int u, int v, double dist, double z)
{
        edge[cnt].u=u;
        edge[cnt].v=v;
        edge[cnt].dist=dist;
        edge[cnt++].z=z;
}
double getdist(N f1, N f2)
{
        return sqrt((f1.x-f2.x)**(f1.x-f2.x)+(f1.y-f2.y)**(f1.y-f2.y));
}
bool cmp(node f1, node f2)
{
        return f1.w<f2.w;
}
void krus(double L)
{
        double ans=;
        int i, f1, f2;
        for(i=;i<cnt;i++){
                edge[i].w=edge[i].z-L*edge[i].dist;
        }
        sort(edge,edge+cnt,cmp);
        for(i=;i<n;i++){
                bin[i]=i;
        }
        int k=;
        p=q=;
        for(i=;i<cnt;i++){
                f1=find1(bin[edge[i].u]);
                f2=find1(bin[edge[i].v]);
                if(f1!=f2){
                        bin[f2]=f1;
                        k++;
                        p+=edge[i].z;
                        q+=edge[i].dist;
                }
                if(k==n-) return ;
        }
}
int main()
{
        int i, u, v, z, j;
        while(scanf("%d",&n)!=EOF&&n){
                for(i=;i<n;i++){
                        scanf("%d%d%d",&dian[i].x,&dian[i].y,&dian[i].z);
                }
                cnt=;
                for(i=;i<n;i++){
                        for(j=;j<i;j++){
                                add(i,j,getdist(dian[i],dian[j]),abs(dian[i].z-dian[j].z)*);
                        }
                }
                double ans=, tmp;
                while(){
                        tmp=ans;
                        krus(tmp);
                        ans=p/q;
                        if(fabs(tmp-ans)<=eqs) break;
                }
                printf("%.3f\n",ans);
        }
        return ;
}