desert king (最优比率生成树).cpp

杭电acm解题报告2001---2099.

//迭代 prime O(N^2) AC
//prime O(NlogN) TLE
//二分枚举 g++ WA, c++ TLE
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;

const int MAX = 1100;
int n;
struct point {
	int x,y,z;
}vi[MAX];
struct node {
	int s, t;
	double dis;
	bool operator < (const node & tt) const {
		return dis > tt.dis;
	}
};
double dist[MAX][MAX];
bool vis[MAX];
double rate;

double prime() {
	double cost = 0;
	double len = 0;
	double d[MAX],v;
	int pre[MAX];
	int i,j;
	memset(vis, 0, sizeof(vis));
	vis[0] = true;
	for(i=1;i<n;i++) {
		d[i] = abs(vi[0].z-vi[i].z) - rate*dist[0][i];
		pre[i] = 0;
	}
	for(i=1;i<n;i++) {
		double minv = INT_MAX;
		int minp = -1;
		for(j=1;j<n;j++) {
			if(!vis[j] && minv > d[j]) {
				minv = d[j];
				minp = j;
			}
		}
		vis[minp] = true;
		cost += abs(vi[pre[minp]].z - vi[minp].z);
		len += dist[pre[minp]][minp];
		for(j=1;j<n;j++) {
			if(!vis[j] && d[j] > (v=abs(vi[minp].z-vi[j].z) - rate*dist[minp][j])) {
				d[j] = v;
				pre[j] = minp;
			}
		}
	}
	return cost / len;
}

int main() {
	int i,j;
	while(scanf("%d", &n), n) {
		for(i=0;i<n;i++) {
			scanf("%d %d %d", &vi[i].x, &vi[i].y,&vi[i].z);
		}
		for(i=0;i<n;i++) {
			dist[i][i] = 0;
			for(j=i+1;j<n;j++) {
				dist[i][j] = dist[j][i] = sqrt(1.0*(vi[i].x-vi[j].x)*(vi[i].x-vi[j].x) + (vi[i].y-vi[j].y)*(vi[i].y-vi[j].y));
			}
		}
		rate = 0;
		while(true) {
			double pre = rate;
			rate = prime();
			if(fabs(rate - pre) < 0.001) break;
		}
		printf("%.3lf\n", rate);
	}
}