poj2728--Desert King（最優比率生成樹）

poj2728--Desert King（最優比率生成樹）

題目大意：給出n個村莊的坐標和高度，給這n個村莊修n-1水管，連接起n個村莊，兩個村莊之間修水管的花費是高度差，距離是歐幾裡得距離（空間距離），要求修的水管的花費和/距離和最小。

按0-1規劃來做，注意求最小生成樹的時候，用prim，因為邊會有n^2條。用c++提交

#include 
#include 
#include 
#include 
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 ;
}