某岛

… : "…アッカリ~ン . .. . " .. .
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