| 题目名称 | 151. [USACO Dec07] 建造路径 |
|---|---|
| 输入输出 | roads.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 BYVoid
于2008-10-06加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：185， 提交：530， 通过率：34.91% | ||||
 donny |
100 | 0.047 s | 1.15 MiB | Pascal |
 joel |
100 | 0.054 s | 9.09 MiB | C++ |
 zjmfrank2012 |
100 | 0.060 s | 7.99 MiB | C++ |
 奶猹 |
100 | 0.063 s | 7.98 MiB | C++ |
 devil |
100 | 0.065 s | 8.12 MiB | C++ |
 hzx |
100 | 0.069 s | 7.19 MiB | C++ |
 Ezio |
100 | 0.069 s | 8.11 MiB | C++ |
 Jim |
100 | 0.079 s | 8.00 MiB | C |
|
Jim |
100 | 0.080 s | 8.00 MiB | C |
 老师，勿删 |
100 | 0.081 s | 8.09 MiB | C++ |
| 本题关联比赛 | |||
| 20091111 | |||
| 20181007 | |||
| 关于 建造路径 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
坑人！
| ||||
|
真tama坑
| ||||
|
得了APWTMECRDT我骄傲
 APWTMECRD
2017-11-01 15:06
11楼
| ||||
|
kruskal数组永远开小。
| ||||
|
事实上我对快排一百万条边能过持怀疑态度，然而评测机跑的就是这么快
 open the window
2016-08-14 11:20
9楼
| ||||
|
把sqrt改成pow就过了!sqrt溢出nun!!
| ||||
|
注意999999*999999的时候int会溢出，调了好久。。。
| ||||
|
Kruskal算法，就是内存有些大
| ||||
|
一开始看到64位浮点数我以为是longdouble。。
顺便问一下longdouble的占位符是什么？ | ||||
|
@digital_T prime不是素数么……= =
 cstdio
2013-10-27 10:03
4楼
| ||||
┭┮﹏┭┮
落痕
Shirry
Riolu
liu_runda
forever
HouJikan译 by CmYkRgB123
【题目描述】
Farmer John 刚刚得到了几个新农场！他想把这几个农场用路连接起来，这样他就可以通过笔直的公路从一个农场到另一个农场了。现在已经有了几条连接着的农场。
N (1 ≤ N ≤ 1,000) 个农场中，每个农场的位置在坐标平面的 (Xi, Yi) (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000)。已经有 M (1 ≤ M ≤ 1,000) 条路以前就被建好了。请你帮助 Farmer John 考虑建设尽量少长度的额外的路，使他的农场连在一起。
【输入格式】
第 1 行: 两个整数: N , M
第 2..N+1 行: 两个整数 Xi , Yi
第 N+2..N+M+2 行: 两个整数: i , j, 表示已经存在从农场i到农场j的路。
【输出格式】
第 1 行: 额外的路的最少长度，保留2小数。 请使用 64 位的浮点数。
【输入样例】
4 1 1 1 3 1 2 3 4 3 1 4
【输出样例】
4.00