公路（最小生成树）

描述

岛屿国家Flatopia是完全平坦的。不幸的是，Flatopia没有公共的公路。所以Flatopia的交通很困难。Flatopian政府意识到这个问题。他们正在计划修建一些高速公路，这样就可以在任何一个城镇之间行驶，而不必离开公路系统。

每个高速公路连接两个城镇。所有高速公路都沿着直线。所有高速公路都可以在两个方向上使用。高速公路可以自由交叉，但驾驶员只能在位于两条高速公路末端的小镇的高速公路之间切换。

Flatopian政府希望减少最长的高速公路的长度。但是，他们希望保证每个城镇都可以从其他城镇进入高速公路。
输入

输入的第一行是一个整数T，它告诉后面有多少个测试用例。
每种情况的第一行是一个整数N（3 <= N <= 500），这是村庄的数量。然后来N行，其中第i个包含N个整数，这N个整数中的第j个是村i和村j之间的距离（距离应该是[1 65536]内的整数）。每个测试用例后都有一个空行。
产量

对于每个测试用例，应该输出一个包含整数的行，这个长度是所有村庄连接的最长路径的长度，这个值是最小的。
示例输入

1

3
0 990 692
990 0 179
692 179 0
示例输出

692

题意：
给图的邻接矩阵，求最小生成树，输出树的最大边

题解：
用Prim算法可参考
保存每次边的权值，最后遍历一次或使用sort排序得到最大边

import java.util.Arrays;
import java.util.Scanner;


public class Test2 {
    private static final int MAX = Integer.MAX_VALUE;
    private static final int N = 505;
    private static int[][] arr = new int[N][N];
    private static int n;

    /**
     * lowcost[i]表示以i为终点的边的最小权值，
     * 当lowcost[i]=0说明以i为终点的边
     * 表示加入了树
     */
    private static int[] lowcost = new int[N];

    public static void prim() {
        int[] sum = new int[n];  //最小生成树的各个权
        int min,k = 0,s=0;
        for (int i = 1; i <= n; i++) {
            lowcost[i] = arr[1][i];    //最初顶点到别点的距离
        }
        for (int i = 1; i <= n; i++) {
            min = MAX;
            for (int j = 1; j <= n; j++) {
                if (lowcost[j]!=0 && lowcost[j] < min) {
                    min = lowcost[j];
                    k = j;
                }
            }

            sum[s] = lowcost[k];
            s++;
            lowcost[k] = 0;

            //更新lowcost
            for (int j = 1; j <= n; j++) {
                if ( lowcost[j]!=0 && arr[k][j] < lowcost[j] ) {
                    lowcost[j] = arr[k][j];
                }
            }
        }
        Arrays.sort(sum);
        System.out.println(sum[s-1]);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int t = 0; t < T; t++) {
            n = sc.nextInt(); //城镇个数
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    arr[i][j] = sc.nextInt();
                }
            }
            prim();
        }

    }
}