2013
11-12

Building Roads

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.

* 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.

* 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.

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

4.00

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(
System.in));
String[] s = read.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
int p1, p2;
double[][] a = new double[n][n];
int[][] p = new int[n][2];
for (int i = 0; i < n; i++) {
s = read.readLine().split(" ");
p[i][0] = Integer.parseInt(s[0]);
p[i][1] = Integer.parseInt(s[1]);
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
a[i][j] = a[j][i] = Math.sqrt(Math.pow(p[i][0] - p[j][0], 2)
+ Math.pow(p[i][1] - p[j][1], 2));
}
}
for (int i = 0; i < m; i++) {
s = read.readLine().split(" ");
p1 = Integer.parseInt(s[0]);
p2 = Integer.parseInt(s[1]);
a[p1 - 1][p2 - 1] = a[p2 - 1][p1 - 1] = 0;
}
System.out.printf("%.2f", prim(a, n));
}

public static double prim(double[][] a, int count) {
double sum = 0;
int i, j, k;
double[] lowcost = new double[count];
double[] closeset = new double[count];
boolean[] used = new boolean[count];
for (i = 0; i < count; i++) {
lowcost[i] = a[0][i];
closeset[i] = 0;
used[i] = false;
}
used[0] = true;
for (i = 1; i < count; i++) {
j = 0;
while (used[j]) {
j++;
}
for (k = 0; k < count; k++) {
if ((!used[k]) && (lowcost[k] < lowcost[j])) {
j = k;
}
}
sum += lowcost[j];
used[j] = true;
for (k = 0; k < count; k++) {
if (!used[k] && (a[j][k] < lowcost[k])) {
{
lowcost[k] = a[j][k];
closeset[k] = j;
}
}
}
}
return sum;
}
}

1. = =。 总觉得内些甜蜜的回忆应该在一只脚踏进鬼门关的时候温习一遍比较有价值。- -。不过LZ你貌似想的跟牛皮筋一样开么。祝你 吃得饱，穿的暖，身高长到178. = =差点想说：祝你年年有今日 岁岁有今朝……（= =我错了。）

2. = =。 总觉得内些甜蜜的回忆应该在一只脚踏进鬼门关的时候温习一遍比较有价值。- -。不过LZ你貌似想的跟牛皮筋一样开么。祝你 吃得饱，穿的暖，身高长到178. = =差点想说：祝你年年有今日 岁岁有今朝……（= =我错了。）

3. = =。 总觉得内些甜蜜的回忆应该在一只脚踏进鬼门关的时候温习一遍比较有价值。- -。不过LZ你貌似想的跟牛皮筋一样开么。祝你 吃得饱，穿的暖，身高长到178. = =差点想说：祝你年年有今日 岁岁有今朝……（= =我错了。）

4. = =。 总觉得内些甜蜜的回忆应该在一只脚踏进鬼门关的时候温习一遍比较有价值。- -。不过LZ你貌似想的跟牛皮筋一样开么。祝你 吃得饱，穿的暖，身高长到178. = =差点想说：祝你年年有今日 岁岁有今朝……（= =我错了。）

5. = =。 总觉得内些甜蜜的回忆应该在一只脚踏进鬼门关的时候温习一遍比较有价值。- -。不过LZ你貌似想的跟牛皮筋一样开么。祝你 吃得饱，穿的暖，身高长到178. = =差点想说：祝你年年有今日 岁岁有今朝……（= =我错了。）

6. = =。 总觉得内些甜蜜的回忆应该在一只脚踏进鬼门关的时候温习一遍比较有价值。- -。不过LZ你貌似想的跟牛皮筋一样开么。祝你 吃得饱，穿的暖，身高长到178. = =差点想说：祝你年年有今日 岁岁有今朝……（= =我错了。）

7. = =。 总觉得内些甜蜜的回忆应该在一只脚踏进鬼门关的时候温习一遍比较有价值。- -。不过LZ你貌似想的跟牛皮筋一样开么。祝你 吃得饱，穿的暖，身高长到178. = =差点想说：祝你年年有今日 岁岁有今朝……（= =我错了。）

8. = =。 总觉得内些甜蜜的回忆应该在一只脚踏进鬼门关的时候温习一遍比较有价值。- -。不过LZ你貌似想的跟牛皮筋一样开么。祝你 吃得饱，穿的暖，身高长到178. = =差点想说：祝你年年有今日 岁岁有今朝……（= =我错了。）

9. 网站做得很好看，内容也多，全。前段时间在博客园里看到有人说：网页的好坏看字体。觉得微软雅黑的字体很好看，然后现在这个网站也用的这个字体！nice!

10. 第二种想法，我想来好久，为啥需要一个newhead，发现是把最后一个节点一直返回到嘴上面这层函数。厉害，这道题之前没样子想过。