题目见上链接(搞得不是太懂,先记下来)。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Arrays; import java.util.Comparator; public class Main { static StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static int[] fa; static class Node { int x, y; long w; Node(int x, int y, long w) { this.x = x; this.y = y; this.w = w; } } static int find(int x) { if (fa[x] == 0) { return x; } return fa[x] = find(fa[x]); } static class Sort implements Comparator<Node> { @Override public int compare(Node o1, Node o2) { if (o1.w < o2.w) return 1; if (o1.w > o2.w) return -1; return 0; } } public static void main(String[] args) throws IOException { int n = nextInt(); int m = nextInt(); Node[] node = new Node[m]; for (int i = 0; i < m; i++) { node[i] = new Node(nextInt(), nextInt(), nextLong()); } fa = new int[n + 1]; Arrays.sort(node, new Sort()); long res = 0; int a, b; for (int i = 0; i < m; i++) { a = find(node[i].x); b = find(node[i].y); if (a == b) continue; fa[a] = b; res += node[i].w; } System.out.println(res); } static int nextInt() throws IOException { streamTokenizer.nextToken(); return (int) streamTokenizer.nval; } static long nextLong() throws IOException { streamTokenizer.nextToken(); return (long) streamTokenizer.nval; } }