agrinet.java

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

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

/**
 * ID:1258
 * PRIM
 * @author yhm
 *
 */
public class AgriNet {

	static int MAXNUM = 100001;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while (cin.hasNext()) {
			int size = cin.nextInt();
			int[][] dis = new int[size][size];
			for (int i = 0; i < size; i++) {
				for (int j = 0; j < size; j++) {
					dis[i][j] = cin.nextInt();
				}
			}

			//solve(dis,size);
			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);
	}
	
	
	
	static void solve(int[][] dis, int size){
		int[] low = new int[size];
		int min, sum = 0;

		//初始化，将第一个点放入
		for (int i = 0; i < size; i++){
			low[i] = dis[0][i];
		}
		low[0] = 0;

		
		for (int i = 1; i < size; i++) {
			min = MAXNUM;
			int j = 1, k = 1;

			//找出下一个点
			while (j < size) {
				if (low[j] > 0 && low[j] < min) {
					min = low[j];
					k = j;
				}
				j++;
			}

			sum += low[k];

			//放入，并更新树到各点的值
			low[k] = 0;

			for (j = 1; j < size; j++) {
				if (dis[k][j] < low[j])
					low[j] = dis[k][j];
			}

		}
		System.out.println(sum);
		
	}

}