01分数规划的题目；
由于是完全图，所以求最小生成树的时候要使用prime算法。
否则的话很容易就超时了。
#include <iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
using namespace std;
#define maxm 1100*1100
#define maxn 1100
#define eps 0.000001
#define zero(x) ((fabs(x)<eps?0:x))
#define INF 99999999
struct point
{
int x;
int y;
int h;
}p[maxn];
double dist(int x,int y)
{
double xx=0;
xx=(p[x].x-p[y].x)*(p[x].x-p[y].x);
xx+=(p[x].y-p[y].y)*(p[x].y-p[y].y);
xx=xx*1.0;
return sqrt(xx);
}
struct list
{
double h;
double l;
double s;
friend bool operator < (const list &a,const list &b)
{
return a.s<b.s;
}
}maps[maxn][maxn];
int m,n;
double prime(double mid)
{
double dis[maxn];
int vis[maxn];
int i,j;
for(i=0;i<=n;i++)
{
dis[i]=INF;
vis[i]=0;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
maps[i][j].s=maps[i][j].h-maps[i][j].l*mid;
}
}
dis[1]=0;
double ans;
ans=0;
while(1)
{
double minn=INF;
int ip;
for(i=1;i<=n;i++)
{
if(vis[i])continue;
if(dis[i]<minn)
{
minn=dis[i];
ip=i;
}
}
if(zero(minn-INF)==0)break;
vis[ip]=1;
ans+=minn;
for(i=1;i<=n;i++)
{
if(vis[i])continue;
dis[i]=min(dis[i],maps[ip][i].s);
}
}
return ans;
}
int main()
{
int i,j;
while(~scanf("%d",&n)&&n)
{
m=0;
for(i=1;i<=n;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].h);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
maps[i][j].h=fabs(p[i].h-p[j].h);
maps[i][j].l=dist(i,j);
}
}
double l,r,mid;
l=0;
r=100;
mid=(l+r)/2;
while(zero(r-l)>0)
{
mid=(l+r)/2;
if(prime(mid)>0)l=mid;
else r=mid;
}
printf("%.3f\n",mid);
}
return 0;
}
poj-2728-Desert King-01分数规划+最小生成树,布布扣,bubuko.com
poj-2728-Desert King-01分数规划+最小生成树
原文：http://blog.csdn.net/rowanhaoa/article/details/23274391