ccf考试201812_4之数据中心

样例输入
4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2
样例输出
4
样例说明
　　下图是样例说明。


代码评分：20
总结：(1)这个题目的难度就在于kruskal算法的编写以及优化。可以看出，我们只需要直接找出kruskal的最小生成树，然后找出树中最大的边即可。
（2）至于为什么评分这么低，可以通过代码的评分细则可以知道，都是因为超时惹的祸，代码做出来以后系统的提示是超时错误。至于怎么优化代码让他不超时我目前还没有更好的办法，代码的思路整体应该没有太大问题。

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //1.初始化数据
        Scanner scanner = new Scanner(System.in);
        int pointNum = scanner.nextInt(); //点得个数
        int sideNum = scanner.nextInt(); //边的个数
        int root = scanner.nextInt(); //根节点

        ArrayList<Side> sides = new ArrayList<Side>();//存放图中的所有边
        for (int i = 0; i < sideNum; i++) {
            int inside = scanner.nextInt();
            int outside = scanner.nextInt();
            int length = scanner.nextInt();
            sides.add(new Side(inside,outside,length));
        }

        ArrayList<Side> result = new ArrayList<Side>();//存放结果

        //2.生成树
        //2.1根节点开始，找到最小生成树放入到result
        //先对sides按照length插入排序，然后使用kruskal
        Side side_temp = null;
        for (int i = 0; i < sides.size() ; i++) {
            //在i到side.size()中找到最小的length的side
            for (int j = i+1; j < sides.size(); j++) {
                //找到最小的side,和side.get(i)交换
                if (sides.get(i).length > sides.get(j).length ){
                    side_temp = sides.get(j);
                    sides.set(j,sides.get(i));
                    sides.set(i,side_temp);
                }
            }
        }

        //2.2每个节点有一个并查集
        int[] bingcha = new int[pointNum+1];
        //bingcha中的第i个节点的根节点为i
        for (int i = 0; i < bingcha.length; i++) {
            bingcha[i] = i;
        }
        //最小生成树的边的个数必定是：点的个数-1
        //直接加入第一个边
        bingcha[sides.get(0).outside] = sides.get(0).inside; //inside为outside的根节点
        result.add(sides.get(0));
        sides.remove(sides.get(0));
        //剩下(pointNum-2)条边
        for (int i = 0; i < (pointNum-2); i++) {
            //遍历sides，加入一条边到result
            for (Side side : sides) {
                int inSideRoot = bingcha[side.inside];
                int outSideRoot = bingcha[side.outside];
                if(inSideRoot == outSideRoot){
                    continue;
                }else {
                    //根节点不同,合并bingcha
                    //所有根节点是outSideRoot都变成inSideRoot
                    for (int k = 0; k < bingcha.length ; k++) {
                        if(bingcha[k] == outSideRoot){
                            bingcha[k] = inSideRoot;
                        }
                    }
                    result.add(side);
                    sides.remove(side);
                    break;
                }
            }
        }


        //3.找到最小生成树中的最长length
        int ans = 0;
        for (Side side : result){
            if( side.length > ans){
                ans = side.length;
            }
        }
        System.out.println(ans);

    }


    //边
    public static class Side{
        int inside;
        int outside;
        int length;

        public Side(int inside, int outside, int length) {
            this.inside = inside;
            this.outside = outside;
            this.length = length;
        }
    }

    //输出ArrayList<Side>
    public static void printArray(ArrayList<Side> arr){
        for (Side side : arr){
            System.out.println(side.inside + " " + side.outside + " " + side.length);
        }
    }
}