jungleroads.java

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

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


/**
 * ID:1251
 * PRIM
 * @author yhm
 *
 */
public class JungleRoads {

	
	static int MAXNUM = 101;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			int size = cin.nextInt();
			if(size==0) break;
			int[][] dis = new int[size][size];
			for(int i=0;i<size;i++){
				Arrays.fill(dis[i], MAXNUM);
			}
			for(int i=0;i<size-1;i++){
				int start = cin.next().charAt(0)-'A';
				int num = cin.nextInt();
				for(int j=0;j<num;j++){
					int end = cin.next().charAt(0)-'A';
					dis[start][end] = cin.nextInt();
					dis[end][start] = dis[start][end];
				}
			}
			
			prim(dis,size);
			
		}

	}
	
	static void prim(int[][] dis, int size){
		int sum=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++){
			int min = MAXNUM;
			int k=1;
			for(int j=1;j<size;j++){
				if(low[j]!=0 && low[j]<min){
					k = j;
					min = low[j];
				}
			}
			sum+=min;
			low[k] = 0;
			for(int j=1;j<size;j++){
				low[j] = Math.min(low[j], dis[k][j]);
			}
		}
		System.out.println(sum);
	}

}