首页 > 专题系列 > Java解POJ > POJ 3625 Building Roads [解题报告] Java
2013
11-12

POJ 3625 Building Roads [解题报告] Java

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. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

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