http://poj.org/problem?id=2728最优比率生成树：这个都可以直接模板来使用了。0-1分数规划，参数搜索，Dinkelbach算法也很好写：
#include<stdio.h>
#include<string.h>
#include<math.h>
#define eps 1e-6
#define inf 1e8
int n,vis[1005],p[1005];
double d[1005][1005],h[1005][1005],g[1005][1005],dis[1005],dt,ht,zl;
double max(double s,double t)
{
if (s>t)
return s;
else
return t;
}
void prim(double L)//这里是找最小生成树，
{
int i,j,minj;
double min;
dt=ht=zl=0;
for (i=1; i<=n ; i++ )
for (j=1; j<=n ; j++ )
g[i][j]=h[i][j]-L*d[i][j];
for (i=1; i<=n ; i++ )
dis[i]=inf,vis[i]=1;
dis[1]=0.0;
p[1]=1;
for (i=1; i<=n ; i++ )
{
min=inf;
for (j=1; j<=n ; j++ )
if (vis[j]&&min>dis[j])
{
min=dis[j];
minj=j;
}
vis[minj]=0;
dt+=d[minj][p[minj]];
ht+=h[minj][p[minj]];
zl+=dis[minj];
for (j=1; j<=n ; j++ )
if (vis[j]&&dis[j]>g[minj][j])
{
dis[j]=g[minj][j];
p[j]=minj;
}
}
}
int main()
{
int i,j;
double maxx,L;
float x[1005],y[1005],z[1005];
while (scanf("%d",&n)==1&&n!=0)
{
for (i=1; i<=n ; i++ )
scanf("%f%f%f",&x[i],&y[i],&z[i]);
maxx=0;
for (i=1; i<=n ; i++ )
for (j=1; j<=n ; j++ )
{
d[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
h[i][j]=fabs(z[i]-z[j]);
maxx=max(maxx,h[i][j]);
}
L=n*maxx; //这个边界条件还可以收敛一些，
while (prim(L),fabs(zl)>eps) L=ht/dt;
printf("%.3lf\n",L);
}
return 0;
}
擦，这个在poj上一下就ac了，hdu上wa，应该是内存的问题吧。不管了，又学会了一个算法，值！叫啥？Dinkelbach算法，迭代下去，挺好写的，算法证明也好理解。那个啥二分法，有时间得写写。0-1分数规划（0-1fractional programming），参数搜索(parametric search)都是好东西呀。
还有好多好多啥prim的堆优化，线形时间复杂度的好多东东不懂，加油啦。