constructingroads.java

PKU中一些数据结构基本算法题的java实现

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


/**
 * ID:2421
 * PRIM
 * @author yhm
 *
 */
public class ConstructingRoads {

	static int size;
	static int[][] M;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		size = cin.nextInt();
		M = new int[size][size];
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				int dis = cin.nextInt();
				M[i][j] = dis==0?Integer.MAX_VALUE:dis;
			}
		}
		int num = cin.nextInt();
		for(int i=0;i<num;i++){
			int row = cin.nextInt()-1;
			int col = cin.nextInt()-1;
			M[row][col] = 0;
			M[col][row] = 0;
		}
		
		prim();

	}
	
	static void prim(){
		int[] low = new int[size];
		boolean[] inS = new boolean[size];
		int sum = 0;
		
		for(int i=0;i<size;i++){
			low[i] = M[0][i];
			inS[i] = false;
		}
		low[0] = 0;
		inS[0] = true;
		
		for(int i=1;i<size;i++){
			int min = Integer.MAX_VALUE;
			int minIndex = 0;
			for(int j=1;j<size;j++){
				if(!inS[j] && low[j]<min){
					min = low[j];
					minIndex = j;
				}
			}
			
			sum += min;
			low[minIndex] = 0;
			inS[minIndex] = true;
			
			for(int j=1;j<size;j++){
				if(!inS[j] && M[minIndex][j]!=Integer.MAX_VALUE && M[minIndex][j]<low[j]){
					low[j] = M[minIndex][j];
				}
			}
			
		}
		System.out.println(sum);
	}

}