POJ-2728-Desert King（最优比率生成树）

题目链接：http://poj.org/problem?id=2728

题目大意：给出一个三维地图，每个村庄包含x，y，z三点坐标。要在村庄之间通上管子。每两个村庄之间的水平距离（x，y）是有效距离。两村庄之间的abs（高度差）是成本。让你找到一个生成树满足 总成本/总有效距离最小。

思路：最优比率生成树板子。对于所有的点：

边权变为：。跑最小生成树即可。

找到一个Ans的最小生成树满足F(Ans)=0即可。

上面的过程得出的是一个单增的一次函数。下面我写的是单减的一次函数。没什么区别（唯一的区别就是正负号，二分时注意移动）。

二分的时候注意上下界，一开始我用的1e7，直接T了。

ACCode：

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
// srand(unsigned)time(NULL));rand();
 
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
 
#define ll long long
#define Pair pair<double,double>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
 
const int MAXN=1e3+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)

struct Point{
	double x,y,z;
};
struct Node{
	double len,val;
	Node(double _len=0,double _val=0){
		len=_len;val=_val;
	}
};
Point Dots[MAXN];
Node MP[MAXN][MAXN];
double Dis[MAXN];
int Vis[MAXN];
int n;

double PoorZ(int i,int j){
	return fabs(Dots[i].z-Dots[j].z);
}
double Distance(int i,int j){
	return sqrt((Dots[i].x-Dots[j].x)*(Dots[i].x-Dots[j].x)+(Dots[i].y-Dots[j].y)*(Dots[i].y-Dots[j].y));
}
int Judge(double mid){
	clean(Vis,0);
	for(int i=1;i<=n;++i) Dis[i]=INF32;
	Dis[1]=0;
	double Sum=0;
	for(int i=1;i<=n;++i){
		int can=-1;double minn=INF32;
		for(int j=1;j<=n;++j){
			if(minn>Dis[j]+EPS&&Vis[j]==0){
				minn=Dis[j];can=j;
			}
		}
		if(can==-1) break;
		Vis[can]=1;Sum+=minn;
		for(int j=1;j<=n;++j){
			if(Vis[j]==0&&MP[can][j].val-mid*MP[can][j].len<Dis[j]){
				Dis[j]=MP[can][j].val-mid*MP[can][j].len;
			}
		}
	}return Sum>0;
}
int main(){
	while(~scanf("%d",&n)){
		if(n==0) break;
		for(int i=1;i<=n;++i){
			scanf("%lf%lf%lf",&Dots[i].x,&Dots[i].y,&Dots[i].z);
		}
		double MaxVal=-INF32,MinVal=INF32,MaxLen=-INF32,MinLen=INF32;
		for(int i=1;i<=n;++i){
			for(int j=i+1;j<=n;++j){
				MP[i][j]=MP[j][i]=Node(Distance(i,j),PoorZ(i,j));
				MaxVal=max(MaxVal,MP[i][j].val);MinVal=min(MinVal,MP[i][j].val);
				MaxLen=max(MaxLen,MP[i][j].len);MinLen=min(MinLen,MP[i][j].len);
			}
		}
		double l=MinVal/MaxLen,r=MaxVal/MinLen,mid;
		while(l<r-EPS){
			mid=(l+r)/2.0;
//			printf("l=%lf r=%lf\n",l,r);
			if(Judge(mid)) l=mid;
			else r=mid;
		}printf("%.3f\n",r);
	}
}

/*
4
0 0 0
0 1 1
1 1 2
1 0 3
0
*/