Poj 2421 Constructing Roads(Prim 最小生成树)

题意：有几个村庄，要修最短的路，使得这几个村庄连通。但是现在已经有了几条路，求在已有路径上还要修至少多长的路。

分析：用Prim求最小生成树，将已有路径的长度置为0，由于0是最小的长度，所以一定会被Prim选中加入最小生成树。

package Map;

import java.util.Scanner;

/**

 * Prime

 */

public class Poj_2421_Prim {

	static int MAXVEX = 200;

	static int n, m;

	static int[][] arc = new int[MAXVEX][MAXVEX];

	static int visited[] = new int[MAXVEX];//判断是否加入生成树

	public static int prime() {

		int min, i, j, k, sum = 0;

		visited[1] = 1;

		for (i = 2; i <= n; i++) {

			min = 1000000;

			k = 0;

			for (j = 1; j <= n; j++) {

				if (visited[j] == 0 && arc[1][j] < min) {

					min = arc[1][j];

					k = j;

				}

			}

			sum += min;

			visited[k] = 1;

			for (j = 1; j <= n; j++) {

				if (visited[j] == 0 && arc[1][j] > arc[k][j]) {

					arc[1][j] = arc[k][j];

				}

			}

		}

		return sum;

	}

	public static void main(String args[]) {

		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();

		for (int i = 1; i <= n; i++) {

			for (int j = 1; j <= n; j++) {

				arc[i][j] = sc.nextInt();

			}

			arc[i][i] = 1000000;

		}

		m = sc.nextInt();

		//如果路径存在，则置为0.这样

		for (int i = 1; i <= m; i++) {

			int s = sc.nextInt();

			int e = sc.nextInt();

			arc[s][e] = 0;

			arc[e][s] = 0;

		}

		System.out.println(prime());

	}

}

巴特西

Poj 2421 Constructing Roads(Prim 最小生成树)

最新文章

热门文章