poj 2728最適比率生成木(国王修運河)

題意:いくつかの点対(x,y,z)が与えられ、ここで(x,y)は点の座標を表し、zはこの点の高さを表す.これらの点は1つの図を構成し、各辺にC(高さ差)と長さL(座標の距離)がかかる.この2つの数はいずれも非負の整数である.1つの生成木を求め、費用の和と長さの和の比を最小にする.すなわち、r=(C 1+C 2+…+Cn-1)/(L 1+L 2+…+Ln-1)最小を求める
考え方:最適比率生成ツリー.この割合がrであると仮定すると、任意のrに対して、r(min)<=r<=r(max)であるべきである.生成ツリーにn-1辺があれば、r(max)*L 1-c 1+...+r(max)*Ln-1-cn-1>=0に整理されます.r(min) *L1-c1+…+r(min) * Ln-1-cn-1<= 0. ここではr(min)を要求するので,2番目の式を重点的に見る.この式は,生成木を構築するスキームが1つ存在する限り,r(min)は必ずこの条件を満たすことを意味する.逆に,r(min)は,すべての生成ツリーを構築するスキームに対して上記式を満たす.
不等式:r*L 1−C 1+…+r*Ln−1−Cn−1<=0の左側の値はrの増加と共に増加し,rの減少と共に減少した.上式をいずれの生成ツリー構築法に対しても成立させるには、rは無限に小さくてもよいが、我々が要求する答えr(min)は、上式をどの構築法においても成立させることができる最大のrの取値である.(x>r(min)であれば、r(min)に対応する取り方は、r=xの場合に不等式が成立しないようにすることができる)
したがって具体的には二分rであり,最大生成ツリーを求めるたびに,新図上の最大生成ツリーの取り方は,老図上の生成ツリーの取り方に対応する.具体的には1つの二分加最大生成ツリーを実現すればよい.最大生成ツリーの書き方は、最小生成ツリーに完全に似ています.

#include <stdio.h>
#include <string.h>
#include <math.h>
#define INF 0x3fffffff
#define N 1005
struct node{
	int x,y,z;
}p[N];
double g[N][N],dis[N];
int n,used[N];
double distance(int i,int j){
	return sqrt((double)((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)));
}
double prim(double r){
	int i,j,now;
	double max,res=0;
	memset(used,0,sizeof(used));
	used[0] = 1;//     prim  ，         
	for(i = 1;i<n;i++)
		dis[i] = r*g[0][i] - abs(p[0].z - p[i].z);//       0   
	for(i = 0;i<n-1;i++){
		max = -INF;
		for(j = 1;j<n;j++)
			if(!used[j] && dis[j] > max){
				now = j;
				max = dis[j];
			}
		used[now] = 1;
		res += max;
		for(j = 1;j<n;j++)
			if(!used[j] && dis[j]<r*g[now][j]-abs(p[now].z-p[j].z))//        
				dis[j] = r*g[now][j]-abs(p[now].z-p[j].z);
	}
	return res;
}
int main(){
	freopen("a.txt","r",stdin);
	while(scanf("%d",&n) && n){
		int i,j;
		double low,high,mid;
		memset(g,0,sizeof(g));
		for(i = 0;i<n;i++)
			scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].z);
		for(i = 0;i<n-1;i++)
			for(j = i+1;j<n;j++)
				g[i][j] = g[j][i] = distance(i,j);
		low = 0,high = 100;//      r
		while(high - low > 1e-7){
			mid = (low+high)/2;
			if(prim(mid)>=0)//              0，     r    
				high = mid;
			else
				low = mid;
		}
		printf("%.3lf
",high);
	}
	return 0;
}