network.java

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

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


/**
 * ID:1861
 * PRIM
 * @author yhm
 *
 */
public class Network {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while (cin.hasNext()) {
			int size = cin.nextInt();
			int num = cin.nextInt();
			int[][] dis = new int[size][size];
			for(int i=0;i<size;i++){
				Arrays.fill(dis[i], Integer.MAX_VALUE);
			}
			for (int i = 0; i < num; i++) {
				int x = cin.nextInt()-1;
				int y = cin.nextInt()-1;
				dis[x][y] = cin.nextInt();
				dis[y][x] = dis[x][y];
			}
			prim(dis,size);

		}

	}
	
	static void prim(int[][] dis, int size){
		int[] low = new int[size];
		boolean[] inS = new boolean[size];
		int[][] edge = new int[size][2];
		List<Integer> xlist = new ArrayList<Integer>();
		List<Integer> ylist = new ArrayList<Integer>();
		int maxLen = Integer.MIN_VALUE;
		for(int i=0;i<size;i++){
			low[i] = dis[0][i];
			edge[i][0] = 0;
			edge[i][1] = 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){
					minIndex = j;
					min = low[j];
				}
			}
			
			maxLen = Math.max(maxLen, min);
			low[minIndex]=0;
			inS[minIndex]=true;
			xlist.add(edge[minIndex][0]);
			ylist.add(edge[minIndex][1]);
			for(int j=1;j<size;j++){
				if(!inS[j] && dis[minIndex][j]<low[j] && dis[minIndex][j] != Integer.MAX_VALUE){
					low[j] = dis[minIndex][j];
					edge[j][0] = minIndex;
					edge[j][1] = j;
				}
			}
			
		}
		
		System.out.println(maxLen);
		Integer[] xR = xlist.toArray(new Integer[0]);
		Integer[] yR = ylist.toArray(new Integer[0]);
		int edgeNum = xR.length;
		System.out.println(edgeNum);
		for(int i=0;i<edgeNum;i++){
			System.out.print((xR[i]+1)+" ");
			System.out.println(yR[i]+1);
		}
		
	}

}