某島

… : "…アッカリ~ン . .. . " .. .
September 9, 2010

POJ 2728. Desert King

Brief description :

現在在n個村莊的地圖坐標和高度,要在他們之間鋪設一些水管, 為了節省預算,只要求構成最小生成樹即可,另外國王希望水管的坡度不會太陡,最小化高度差與長度的比值。

Analyse :

恐怕這個就是經典的最優比率生成樹。。。#

/*
    Author  : xiaodao
    Problem : POJ 2728. Desert King
    Status  : Accepted
    Last Modify : GMT +8. Sept 9th 15:43.
    Tags : 最優比率生成樹

*/
#include 
#include 
#include 
using namespace std;
const double EPS = 1e-6, INF = 1e9;
const int N = 1000;
struct po{
    double x, y; int h;
    double k; bool c;
} P[N];
int n;
double ans;


inline int cost(int a, int b){
    return abs(P[a].h-P[b].h);
}

inline double dist(int a, int b){
    return sqrt((P[a].x-P[b].x)*(P[a].x-P[b].x) + (P[a].y-P[b].y)*(P[a].y-P[b].y));
}


inline int Extract(){
    int i = 0, h;
    while (P[i].c) i++; h = i;
    for (i++;i 0) l = m;
        else r = m;
    }
    ans = l;
}

void init(){
    for (int i=0;i

External link :

http://acm.pku.edu.cn/JudgeOnline/problem?id=2728
http://hi.baidu.com/%8E%E1%D0%B3/blog/item/199c38d4e614762207088bf0.html