poj 1287 最小生成树

好久没写过了，wa了很多次才过，真水

import java.util.Scanner;

public class Main {

    public static void main(String args[]) throws Exception {
        Scanner cin = new Scanner(System.in);
        String line = null;
        while (!(line = cin.nextLine().trim()).equals("0")) {
            if (line.trim().equals("")) {
                continue;
            }
            int point = Integer.parseInt(line.split(" ")[0]);
            int range = Integer.parseInt(line.split(" ")[1]);

            int[][] g = new int[point + 1][point + 1];
            for (int i = 0; i < range; i++) {
                String l = cin.nextLine();
                String[] ls = l.split(" ");
                int from = Integer.parseInt(ls[0]);
                int to = Integer.parseInt(ls[1]);
                int value = Integer.parseInt(ls[2]);
                if (g[from][to] > 0) {
                    g[from][to] = g[to][from] = Math.min(g[from][to], value);
                } else {
                    g[from][to] = g[to][from] = value;
                }
            }

            int r = kruskal(g);
            System.out.println(r);
        }
    }

    private static int kruskal(int[][] g) {
        // result[a][b]>0 代表a-->b已经加入到生成树中
        int[][] result = new int[g.length][g.length];

        int[] father = new int[g.length];
        for (int i = 0; i < g.length; i++) {
            father[i] = i;
        }

        // 已经遍历过的边 result是visit的子集
        int[][] visit = new int[g.length][g.length];

        // 当所有节点都已经加入到生成树中 退出循环
        while (!allInOneTree(father)) {
            int min = Integer.MAX_VALUE;
            int a = 0;
            int b = 0;
            for (int i = 1; i < g.length; i++) {
                for (int j = 1; j < i; j++) {
                    // 代表没有访问过的边
                    if (visit[i][j] == 0) {
                        if (g[i][j] > 0 && g[i][j] < min) {
                            min = g[i][j];
                            a = i;
                            b = j;
                        }
                    }
                }
            }
            visit[a][b] = visit[b][a] = g[a][b];
            if (!circle(father, a, b)) {
                result[a][b] = result[b][a] = g[a][b];
                unionSet(father, a, b);
            }
        }

        return printResult(result);
    }

    private static int printResult(int[][] result) {
        int r = 0;
        for (int i = 1; i < result.length; i++) {
            for (int j = 1; j < i; j++) {
                r += result[i][j];
                // System.err.print(String.format("%3d", result[i][j]));
            }
            // System.err.println();
        }
        // System.out.println(r);
        return r;
    }

    public static int dfsSet(int[] father, int x) {
        return father[x] == x ? x : dfsSet(father, father[x]);
    }

    public static void unionSet(int[] father, int a, int b) {
        a = dfsSet(father, a);
        b = dfsSet(father, b);
        if (a != b) {
            if (a > b) {
                father[a] = b;
            } else {
                father[b] = a;
            }
        }
    }

    private static boolean allInOneTree(int[] father) {
        for (int i = 1; i < father.length; i++) {
            if (dfsSet(father, i) > 1) {
                return false;
            }
        }
        return true;
    }

    /**
     * 判断是否有回路(加进来之前判断是否可达 dfs)
     */
    private static boolean circle(int[] father, int a, int b) {
        return dfsSet(father, a) == dfsSet(father, b);
    }

    private static void print(int[][] g) {
        for (int i = 1; i < g.length; i++) {
            for (int j = 1; j < g.length; j++) {
                System.err.print(String.format("%3d", g[i][j]));
            }
            System.err.println();
        }
    }

}