highways.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 71 行

package PKU.PRIM;
import java.util.*;


/**
 * ID:2485
 * PRIM
 * @author yhm
 *
 */
public class Highways {

	static int MAXNUM=65537;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int caseNum = cin.nextInt();
		for(int i=0;i<caseNum;i++){
			int size = cin.nextInt();
			int[][] dis = new int[size][size];
			/*for(int j=0;j<size;j++){
				Arrays.fill(dis[j], MAXNUM);
			}*/
			for(int j=0;j<size;j++){
				for(int k=0;k<size;k++){
					dis[j][k] = cin.nextInt();
				}
			}
			
			prim(dis,size);
			
		}

	}

	
	static void prim(int[][] dis, int size){
		int min=0, maxEdge=0, minIndex=0;
		int[] low = new int[size];
		for(int i=0;i<size;i++){
			low[i]=dis[0][i];
		}
		low[0]=0;
		
		for(int i=1;i<size;i++){
			min = MAXNUM;
			for(int j=1;j<size;j++){
				if(low[j]!=0&&low[j]<min){
					min = low[j];
					minIndex = j;
				}
			}
			
			maxEdge = Math.max(maxEdge, min);
			
			low[minIndex] = 0;
			for(int j=1;j<size;j++){
				low[j] = Math.min(low[j], dis[minIndex][j]);
			}
			
		}
		
		System.out.println(maxEdge);
		

		
	}
}