poj2728 Desert King——01分数规划

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

第一道01分数规划题！(其实也蛮简单的)

这题也可以用迭代做(但是不会)，这里用了二分；

由于比较裸，不作过多说明了。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define eps 1e-6

using namespace std;

int const inf=0x3f3f3f;

int n;

double d[][],h[][],w[][],dis[];

double xx[],yy[],zz[];

bool vis[];

void add(int x,int y)

{

    double ds=sqrt((xx[x]-xx[y])*(xx[x]-xx[y])+(yy[x]-yy[y])*(yy[x]-yy[y]));

    d[x][y]=d[y][x]=ds;

    h[x][y]=h[y][x]=fabs(zz[x]-zz[y]);

}

double prim(double mid)

{

    double s=;

    for(int i=;i<n;i++)

        for(int j=i+;j<n;j++)

            w[i][j]=w[j][i]=h[i][j]-mid*d[i][j];

    for(int i=;i<n;i++)vis[i]=,dis[i]=inf;

    dis[]=;

    while()

    {

        int u=-;

        for(int i=;i<n;i++)

            if(!vis[i]&&(u==-||dis[i]<dis[u]))u=i;

        if(u==-)break;

        s+=dis[u];vis[u]=;

        for(int i=;i<n;i++)

            if(!vis[i])dis[i]=min(dis[i],w[u][i]);

    }

    return s;

}

int main()

{

    while(~scanf("%d",&n))

    {

        if(!n)return ;

        for(int i=;i<n;i++)

            scanf("%lf%lf%lf",&xx[i],&yy[i],&zz[i]);

        for(int i=;i<n;i++)

            for(int j=i+;j<n;j++)

                add(i,j);

        double l=,r=100.00;//

        while(r-l>eps)

        {

            double mid=(l+r)/;

            if(prim(mid)<eps)r=mid;//

            else l=mid;

        }

        printf("%.3lf\n",r);

    }

}