题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2966
中文大意
去年冬天，华南发生了一场大雪。电力系统严重损坏，许多村庄市区了与主电网的联系。计算最小重建的成本，确保至少有一条线路在两个村庄之间。例子中，1代表1个测试用例，第二行代表村庄的数量N和在村庄之间的原始输电线的数量E，随后E行，每行有三个整数A、B、K，A 和 B 分别表示电力线的起始村庄和结束村庄的索引。如果 K 是 0, 这意味着这条线在暴风雪后仍然工作正常。如果 k 是正整数, 则表示此行将花费 K 进行重建。任意两个村庄之间最多只能有一条线。
核心思路
套用并查集路径压缩的模板。由于时间的限制，用快速输入输出流的形式避免超时。
代码：
import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Main { private int[] parent; private int[] weight; private int size; private int group;//有几组 public Main(int size) { this.parent = new int[size]; this.weight = new int[size]; this.size = size; this.group=size; for (int i = 0; i < size; i++) { this.parent[i] = i; this.weight[i] = 1; } } //寻找这个元素属于哪个集合 public int find(int element) { while (element != parent[element]) { parent[element] = parent[parent[element]]; element = parent[element]; } return element; } //判断两个元素之间是否有关系 public boolean isConnected(int firstElement, int secondElement) { return find(firstElement) == find(secondElement); } //合并两个元素 public void unionElements(int firstElement, int secondElement) { int firstRoot = find(firstElement); int secondRoot = find(secondElement); //如果已经属于同一个集合了，就不用再合并了。 if (firstRoot == secondRoot) { return; } if (weight[firstRoot] > weight[secondRoot]) { parent[secondRoot] = firstRoot; weight[firstRoot] += weight[secondRoot]; } else {//weight[firstRoot] <= weight[secondRoot] parent[firstRoot] = secondRoot; weight[secondRoot] += weight[firstRoot]; } group--; } public int getGroup() { return group; } public static void main(String[] args) { StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out)); try { while(sc.nextToken()!=StreamTokenizer.TT_EOF) { int t=(int) sc.nval; while(t-->0) { sc.nextToken(); int n=(int) sc.nval; sc.nextToken(); int e=(int) sc.nval; Main h=new Main(n); List<Hamlet> list=new ArrayList<Hamlet>(); for(int i=0;i<e;i++) { sc.nextToken(); int x=(int) sc.nval; sc.nextToken(); int y=(int) sc.nval; sc.nextToken(); int z=(int) sc.nval; list.add(new Hamlet(x,y,z)); } Collections.sort(list); int sum=0; for (int i = 0; i < list.size(); i++) { if (h.getGroup() > 1) { if (!h.isConnected(list.get(i).a,list.get(i).b)) { h.unionElements(list.get(i).a,list.get(i).b); sum += list.get(i).k; } } } System.out.println(sum); } } } catch (IOException e) { e.printStackTrace(); } } } class Hamlet implements Comparable<Hamlet>{ int a; int b; int k; public Hamlet(int a, int b, int k) { this.a = a; this.b = b; this.k = k; } @Override public int compareTo(Hamlet h) { if(k>h.k)return 1; else if(k<h.k) { return -1; } return 0; } }
