題意:
有n個點,要求一棵生成樹使總height/distance最小,height為兩點高度差,distance為兩點間距離,輸出最小的height/distance。
解題思路:
這題是01規劃在最小生成樹中的應用,我們按照01規劃的方法不斷求優化斜率,在更新斜率的時候用求最小生成樹的做法去使height-l*distance(l就是斜率,即要求的答案)的值最大,然後更新l到不能再更新為止就可以了。
不會01規劃的可以去看這篇部落格
http://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.html
代碼:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=1005;
const double eps=1e-9;
int top;
int n;
struct p
{
double x;
double y;
double z;
}a[maxn];
struct node
{
int x;
int y;
double c;
double d;
double e;
}edg[maxn*maxn];//邊數是點數的平方
int f[maxn];
int getf(int x)
{
if(x==f[x])return x;
else return f[x]=getf(f[x]);
}
bool merg(int x, int y)
{
int a=getf(x);
int b=getf(y);
if(a!=b)
{
f[a]=b;
return 1;
}
else return 0;
}
double dis(int x, int y)
{
return sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));
}
bool cmp(node a, node b)
{
return a.e<b.e;
}
double ff(double l)
{
int i, j=0;
for(i=1; i<=n; i++)f[i]=i;
for(i=0; i<top; i++)edg[i].e=edg[i].c-l*edg[i].d;
sort(edg, edg+top, cmp);
double fz=0, fm=0;
for(i=0; i<top; i++)
{
if(merg(edg[i].x, edg[i].y))
{
fz+=edg[i].c;
fm+=edg[i].d;
// printf("%d %d %.3f %.3f %.3f\n", edg[i].x, edg[i].y, l, edg[i].c, edg[i].d);
j++;
}
if(j==n-1)break;
}
// printf("%.3f\n", fz/fm);
return fz/fm;
}
int main()
{
int i, j;
double e, l;
while(~scanf("%d", &n))
{
if(n==0)break;
top=0;
for(i=1; i<=n; i++)
{
scanf("%lf%lf%lf", &a[i].x, &a[i].y, &a[i].z);
for(j=1; j<i; j++)
{
edg[top].x=i;
edg[top].y=j;
edg[top].d=dis(i, j);
edg[top++].c=fabs(a[i].z-a[j].z);
}
}
e=edg[0].c/edg[0].d;
while(1)
{
l=ff(e);
if(fabs(l-e)<eps)break;
e=l;
}
printf("%.3f\n", l);
}
return 0;
}