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
