poj 2728--Desert King(最適比率生成ツリー)
1974 ワード
poj 2728:タイトルリンク
nの村の座標と高さを与えて、このnの村にn-1の水道管を修理して、nの村を接続して、2つの村の間の水道管の修理の費用は高さの差で、距離はユークリッドの距離(空間の距離)で、修理する水道管の費用と/距離と最小を要求します.
0-1計画で行い、最小生成ツリーを求めるときはprimを使います.辺にn^2本あるからです.c++でコミット
nの村の座標と高さを与えて、このnの村にn-1の水道管を修理して、nの村を接続して、2つの村の間の水道管の修理の費用は高さの差で、距離はユークリッドの距離(空間の距離)で、修理する水道管の費用と/距離と最小を要求します.
0-1計画で行い、最小生成ツリーを求めるときはprimを使います.辺にn^2本あるからです.c++でコミット
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std ;
#define eqs 1e-6
#define INF 0x3f3f3f3f
struct point{
double x , y , z ;
}p[1100] ;
int vis[1100] , n ;
double dis[1100] ;
double low , mid , high ;
double f(int i,int j,double mid) {
return fabs(p[i].z-p[j].z) - mid*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) ) ;
}
double solve(double mid) {
int i , j , id , u ;
double ans = 0 , min1 ;
memset(vis,0,sizeof(vis)) ;
for(i = 0 ; i < n ; i++) dis[i] = INF ;
vis[0] = 1 ; dis[0] = 0 ; u = 0 ;
for( i = 1 ; i < n ; i++ ) {
min1 = INF ; id = 0 ;
for(j = 0 ; j < n ; j++) {
if( vis[j] ) continue ;
dis[j] = min( dis[j],f(u,j,mid) ) ;
if( min1-dis[j] >= eqs ) {
min1 = dis[j] ;
id = j ;
}
}
ans += min1 ;
vis[id] = 1 ;
u = id ;
}
return ans ;
}
int main() {
int i , j ;
double temp , max1 , min1 ;
while( scanf("%d", &n) && n ) {
low = high = mid = 0.0 ;
max1 = 0 ; min1 = INF ;
for(i = 0 ; i < n ; i++) {
scanf("%lf %lf %lf", &p[i].x, &p[i].y, &p[i].z) ;
min1 = min(min1,p[i].z) ;
max1 = max(max1,p[i].z) ;
}
high = (max1-min1)*n ;
while( high - low > eqs) {
mid = (low + high) / 2.0 ;
temp = solve(mid) ;
if( fabs(temp) < eqs ) break ;
if( temp < 0 ) high = mid ;
else low = mid ;
}
printf("%.3f
", mid) ;
}
return 0 ;
}