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 閱讀(130)
評論(0) 編輯 收藏 引用