| 题目名称 | 3476. [POJ 2728]沙漠之王 |
|---|---|
| 输入输出 | desertking.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 syzhaoss
于2020-09-18加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：10， 提交：30， 通过率：33.33% | ||||
 op_组撒头屯 |
100 | 1.044 s | 15.86 MiB | C++ |
|
小金 |
100 | 1.324 s | 10.67 MiB | C++ |
 东条林荫 |
100 | 1.595 s | 22.10 MiB | C++ |
|
瑆の時間~無盡輪迴·林蔭 |
100 | 1.707 s | 26.52 MiB | C++ |
|
yrtiop |
100 | 1.965 s | 13.45 MiB | C++ |
|
op_组撒头屯 |
100 | 2.115 s | 18.59 MiB | C++ |
 策 |
100 | 2.169 s | 13.45 MiB | C++ |
 cqw |
100 | 2.662 s | 14.46 MiB | C++ |
|
dsn |
100 | 5.464 s | 4.03 MiB | C++ |
|
嗨嗨嗨 |
100 | 5.557 s | 25.61 MiB | C++ |
| 关于 沙漠之王 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
| ||||
|
那个男人他复出了
东条林荫
2020-10-12 23:42
2楼
| ||||
|
数据千万条，
清空第一条。 多测不清空， 爆零两行泪。 瑆の時間~無盡輪迴·林蔭
2020-10-12 23:42
1楼
| ||||
【题目描述】
大卫大帝刚刚建立了一个沙漠帝国，为了赢得他的人民的尊重，他决定在全国各地建立渠道，为每个村庄提供水源。与首都相连的村庄将得到水资源的浇灌。他希望构建的渠道可以实现单位长度的平均成本降至最低。换句话说，渠道的总成本和总长度的比值能够达到最小。
他只希望建立必要的渠道，为所有的村庄提供水资源，这意味着每个村庄都有且仅有一条路径连接至首都。他的工程师对所有村庄的地理位置和高度都做了调查，发现所有渠道必须直接在两个村庄之间水平建造。由于任意两个村庄的高度均不同，所以每个渠道都需要安装一个垂直的升降机，从而使得水能够上升或下降。建设渠道的成本只跟升降机的高度有关，换句话说只和渠道连接的两个村庄的高度差有关。
需注意，所有村庄（包括首都）的高度都不同，不同渠道之间不能共享升降机。
【输入格式】
输入包含多组测试数据。
每组测试数据第一行包含整数n，表示村庄（包括首都）的总数目。
接下来N行，每行包含三个整数x，y，z，描述一个村庄的地理位置，(x,y)为该村庄的位置坐标，z为该村庄的地理高度。
第一个被描述的村庄即为首都。
当输入一行为0时，表示输入终止。
【输出格式】
每组数据输出一个结果，每个结果占一行。
结果为一个保留三位小数的实数，表示渠道的总成本和总长度的比值的最小值。
【样例输入】
4 0 0 0 0 1 1 1 1 2 1 0 3 0
【样例输出】
1.000
【数据范围与约定】
$2\leq n\leq 1000$，
$0\leq x,y<10000$，
$0\leq z\leq 10^7$。
【来源】
《算法竞赛进阶指南》