http://poj.org/problem?id=2728最優(yōu)比率生成樹：這個(gè)都可以直接模板來(lái)使用了。0-1分?jǐn)?shù)規(guī)劃，參數(shù)搜索，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; //這個(gè)邊界條件還可以收斂一些，
while (prim(L),fabs(zl)>eps) L=ht/dt;
printf("%.3lf\n",L);
}
return 0;
}
擦，這個(gè)在poj上一下就ac了，hdu上wa，應(yīng)該是內(nèi)存的問(wèn)題吧。不管了，又學(xué)會(huì)了一個(gè)算法，值！叫啥？Dinkelbach算法，迭代下去，挺好寫的，算法證明也好理解。那個(gè)啥二分法，有時(shí)間得寫寫。0-1分?jǐn)?shù)規(guī)劃（0-1fractional programming），參數(shù)搜索(parametric search)都是好東西呀。
還有好多好多啥prim的堆優(yōu)化，線形時(shí)間復(fù)雜度的好多東東不懂，加油啦。