题目介绍
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了连接两个城镇需要花费的代价。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少花费多少代价就可以完成工程？
Input
输入包含多组数据，对于每组测试数据：
第一行包含两个正整数N和M(0 <=N <=1000,0 < M < 5000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以1～N编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0 < A,B <= N ,0 < X < 10000),表示可以在城镇A和城镇B之间建一条花费为X的双向道路。保证数据可以完成工程。
Output
对于每组数据，输出完成工程需要花费的最少代价。
Sample Input
3 3
1 2 3
1 3 1
2 3 2
Sample Output
3
题目思路
利用并查集来维护城市间是否连通。每次寻找花费最少且未被标记的道路并且标记，如果该道路两头未连通，则累加到总花费中。直至找不到输出总花费。
具体代码
package com.dreamchaser; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * kruskal算法的实现（并查集） */ public class test5 { /** * 记录城市连通情况 * 下标为零的不算数 */ static int[] city; static List<Road> roads = new ArrayList<Road>(); /** * 现有城镇的数目 */ static int n; /** * 能修建的道路的数目 */ static int m; public static void main(String[] args) { input(); System.out.println("最少所需费用为："); System.out.println(caculate()); } /** * 计算费用 * 按价格遍历所有可行的道路，将未连通的道路费用加上并合并所在集合 * @return */ private static int caculate() { int total=0; Road road=findMin(); while (road!=null){ if (merge(road.begin, road.end)!=0){ total+=road.money; } //标记已经遍历 road.flag=true; road=findMin(); } return total; } /** * 寻找最短可行路径 * @return */ private static Road findMin() { Road minRoad=null; for (Road road:roads){ if (minRoad==null){ if (!road.flag){ minRoad=road; } }else if(!road.flag&&road.money< minRoad.money){ minRoad=road; } } return minRoad; } private static void input() { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); //输入道路信息 for (int i = 0; i < m; i++) { Road road = new Road(scanner.nextInt(), scanner.nextInt(), scanner.nextInt()); roads.add(road); } city = new int[n+1]; } /** * 寻找根节点 * * @param i * @return */ private static int findUnion(int i) { /** * 合并集的根 */ if (city[i] != 0) { int root = findUnion(city[i]); //路径压缩 city[i] = root; return root; } else { return i; } } /** * 合并集合 * 如果两个属于同一个集合则返回null，否则返回根节点 * @param x * @param y * @return */ private static int merge(int x, int y) { int root1 = findUnion(x); int root2 = findUnion(y); if (root1 != root2) { city[root2] = root1; return root1; } else { return 0; } } static class Road { int begin; int end; int money; /** * 标记有没有走过 */ Boolean flag=false; public Road(int begin, int end, int money) { this.begin = begin; this.end = end; this.money = money; } } }
运行截图
