AcWing 858. Prim算法求最小生成树
原题链接
简单
朴素prim算法,适用于稠密图求最小生成树
注意要与dijkstra算法做对比
import java.util.*;
public class Main {
static final int N = 510;
static final int M = 100010;
static final int INF = 0x3f3f3f3f;
static int n;
static int m;
static int[] dist = new int[N]; // 表示该点到集合的距离
static int[][] g = new int[N][N];
static boolean[] st = new boolean[N];
private static int prim() {
Arrays.fill(dist, INF);
int res = 0;
for (int i = 0; i < n; i++) {
int t = -1;
for (int j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 特判如果是第1次迭代,集合中就第1个点,图不是不连通,也还没有距离
if (i != 0 && dist[t] == INF) return INF;
if (i != 0) res += dist[t];
st[t] = true;
// 这里与最小生成树不同,不是更新所有点到起点的距离,而是更新所有点到集合的距离
for (int j = 1; j <= n; j++) dist[j] = Math.min(dist[j], g[t][j]);
}
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
// 去除自环
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i == j) g[i][j] = 0;
else g[i][j] = INF;
while (m-- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
int w = sc.nextInt();
// 去除重边
g[a][b] = Math.min(g[a][b], w);
g[b][a] = Math.min(g[b][a], w);
}
int t = prim();
if (t == INF) System.out.println("impossible");
else System.out.println(t);
}
}