posts - 74,  comments - 33,  trackbacks - 0
Building Roads
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2219 Accepted: 670

Description

Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can travel from any farm to any other farm via a sequence of roads; roads already connect some of the farms.

Each of the N (1 ≤ N ≤ 1,000) farms (conveniently numbered 1..N) is represented by a position (Xi, Yi) on the plane (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000). Given the preexisting M roads (1 ≤ M ≤ 1,000) as pairs of connected farms, help Farmer John determine the smallest length of additional roads he must build to connect all his farms.

Input

* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Two space-separated integers: Xi and Yi
* Lines N+2..N+M+2: Two space-separated integers: i and j, indicating that there is already a road connecting the farm i and farm j.

Output

* Line 1: Smallest length of additional roads required to connect all farms, printed without rounding to two decimal places. Be sure to calculate distances as 64-bit floating point numbers.

Sample Input

4 1
1 1
3 1
2 3
4 3
1 4

Sample Output

4.00

Source

USACO 2007 December Silver
就是prim7点半开始搞,打了10分钟的代码,提交WA,Faint一直改啊改,结果刚才看看自己的distance函数用了sqrtf,心想64位的就用它了
没想到阴沟里翻船!Faint,题目简单就是简单prim晕了因为sqrtf错了近20次,我可以跳海了
代码直接找本数据结构的数就有prim
posted on 2009-04-02 21:50 KNIGHT 阅读(123) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年4月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

常用链接

留言簿(8)

随笔档案

文章档案

Friends

OJ

搜索

  •  

最新评论

阅读排行榜

评论排行榜