牛客练习赛69——C 旅行

题目见上链接（搞得不是太懂，先记下来）。

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;
    }
}