学步园

       题意：在二维平面内有一些点，每个点都有一个高度（变成三维了），现要找一个生成树，使得高度和除以距离和最小。（n<=1000,x,y<10000, z<10000000） 

       分析：二分比值，然后求最小生成树，判断结果是否大于0。。。用二分会超时，用牛顿迭代法，实质是不断逼近迭代。

#include<stdio.h>
#include<queue>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;

const int maxn=1100;
struct point
{
	double x,y,z;
}p[maxn];

int n;
double d[maxn][maxn],h1[maxn],d1[maxn],h[maxn][maxn];

double Abs(double a)
{
	return a>0? a:-a;
}
int main()
{
	int i,j,k;
	bool flag[maxn];
	double mid,sumh,sumd;
	while(scanf("%d",&n)!=EOF)
	{
		if(!n) break;
		for(i=0;i<n;i++)
			scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
		for(i=0;i<n;i++)//计算任意两点的高度差与平面坐标的距离
		{
			h[i][i]=0;
			d[i][i]=0;
			for(j=i+1;j<n;j++)
			{
				h[i][j]=h[j][i]=Abs(p[i].z-p[j].z);
				d[i][j]=d[j][i]=sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
			}
		}

		mid=0;//迭代求最后的比值
		while(1)
		{
			memset(flag,false,sizeof(flag));
			for(i=0;i<n;i++)
			{
				h1[i]=h[0][i];
				d1[i]=d[0][i];
			}
			flag[0]=true;
			for(sumh=0,sumd=0,i=1;i<n;i++)
			{
				j=1;
				while(flag[j]) j++; 
				k=j;
				for(j++;j<n;j++)//每次加入最小的
					if(!flag[j]&&h1[j]-mid*d1[j]<h1[k]-mid*d1[k])
						k=j;
				flag[k]=true;
				sumh+=h1[k];//总高度
				sumd+=d1[k];//总距离
				for(j=1;j<n;j++)//更新
					if(!flag[j]&&h1[j]-mid*d1[j]>h[k][j]-mid*d[k][j])
					{
						h1[j]=h[k][j];
						d1[j]=d[k][j];
					}
			}
			if(fabs(mid-sumh/sumd)<0.00001) break;
			mid=sumh/sumd;//迭代
		}
		printf("%.3lf\n",mid);
	}
	return 0;
}