公路（最小生成树）

╰半夏微凉° 2022-06-06 11:20 159阅读 0赞

描述

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

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

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

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

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

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

692

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

题解：  
用Prim算法[可参考][Link 1]  
保存每次边的权值，最后遍历一次或使用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();
            }
    
        }
    }

[Link 1]: http://blog.csdn.net/yeruby/article/details/38615045