prim求最小生成树——Highways

电玩女神 2022-08-21 03:22 189阅读 0赞

Highways  
Time Limit: 1000MS Memory Limit: 65536K  
Total Submissions: 27038 Accepted: 12363  
Description

The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways.  
So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem.  
They’re planning to build some highways so that it will be possible to drive between any pair  
of towns without leaving the highway system.

Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways  
follow straight lines. All highways can be used in both directions. Highways can freely cross  
each other, but a driver can only switch between highways at a town that is located at the end  
of both highways.

The Flatopian government wants to minimize the length of the longest highway to be built. However,  
they want to guarantee that every town is highway-reachable from every other town.  
Input

The first line of input is an integer T, which tells how many test cases followed.  
The first line of each case is an integer N (3 <= N <= 500), which is the number of villages.  
Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the  
distance (the distance should be an integer within \[1, 65536\]) between village i and village j.  
There is an empty line after each test case.  
Output

For each test case, you should output a line contains an integer, which is the length of the  
longest road to be built such that all the villages are connected, and this value is minimum.  
Sample Input

3  
0 990 692  
990 0 179  
692 179 0  
Sample Output

692

生成树：给定一个无向图，如果它的某个子图包含原图中的所有点并且其其中的任意两个点都互相连通并且是一棵树，哪么这棵树就叫做生成树（Spanning Tree)。  
最小生成树：如果给定的图的边上是有权值的，哪么使得**边权和最小**的生成树就叫做最小生成树（MST：Minimum Spanning Tree)  
常见的求解最小生成树的算法有Kruskal算法和Prim算法，其时间复杂度都为O(|E|·log|V|)，其中|E|为图中的边数，|V|为顶点数。  
注意：生成树是否存在和图是否连通是等价的，所以只有是连通图才能求最小生成树！！

Prim算法和Dijkstra算法十分相似，都是从某个顶点出发，不断添加边。

用集合V表示给定的图的顶点的集合，X是维护当前最小生成树的顶点的集合。  
由于最小生成树是连接所有顶点的，所以一开始可以选择V中的任何一个顶点  
将其放入X中接着进行扩展。  
维护一个一维数组minCost\[\]用以表示当前X（注意是最小生成树的集合，包含多个顶点，单位上升到了点的集合，而非一个顶点）到V\\X（这表示V中除去X中的顶点剩下的点的集合）的距离，然后从minCost\[\]中选取一个最小的值minCost\[u\]（当然前提是u在V\\X中，这就需要一个标志数组used\[\]来进行维护），并且将u加入到X中，**注意：不要忘记minCost的含义，它是用来选取V到V\\X的最小边的，所以每当一个新的元素u加入到了V\\X中，就需要对minCost进行维护，使其时刻代表着最小的权值边，便于下次的选取，由于受到影响的边只是刚刚加入的与u相连的边，所以一个可以通过一个循环：minCost\[u\]=Min(minCost\[u\],cost\[u\]\[v\]实现**

数据结构：

1.  cost\[\]\[\]:输入的图的边是有权值的，所以用一个二维数组cost用以存储图
2.  minCost\[\]:用以存储从集合X（最小生成树的集合）出发的边到每个顶点的最小权值
3.  used\[\]:标记数组，看元素是否在X中

***注意一开始cost，minCost一开始应初始化为INF，used初始化为false!***

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main {
    
        public static final int INF = 1000000000;
        public static int M;
        public static int[][] cost;
        public static boolean[] used;
        public static int[] minCost;
    
        public static void init(){
            Arrays.fill(minCost, INF);
            Arrays.fill(used, false);
            for(int i=0;i<M;i++){
                for(int j=0;j<M;j++) cost[i][j] = INF;
            }
        }
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            int N = in.nextInt();
            while((N--)>0){
                M = in.nextInt();
                cost = new int[M+10][M+10];
                used = new boolean[M+10];
                minCost = new int[M+10];
                init();
                for(int i=0;i<M;i++){
                    for(int j=0;j<M;j++){
                        cost[i][j] = in.nextInt();
                    }
                }
                minCost[0] = 0;//初始点
                int res = -1;
                while(true){
                    int v = -1;
                    /*从不属于X的顶点中选取从X到其权值最小的顶点，注意这里的v，既代表了所需要选取的顶点，又起到了一个标志作用*/
                    for(int u=0;u<M;u++){
                        if(!used[u]&&(v==-1||minCost[u]<minCost[v])) v = u;
                    }
                    /*v=-1只有一中情况，那就是所有的元素都已经包含在最小生成树中了，因为"int v=-1;if(!used[u]&&(v==-1||minCost[u])",&&具有短路作用，每次while循环只要执行到了“v==-1||minCost[u])”，v就一定不是-1了。*/
                    if(v==-1) break;
                    used[v] = true;
                    if(res<minCost[v]) res = minCost[v];
                    //更新
                    for(int u=0;u<M;u++){
                        minCost[u] = Math.min(minCost[u],cost[u][v]);
                    }
                }
                System.out.println(res);
            }
    
        }
    
    }