AcWing 1140. 最短网络
原题链接
简单
作者:
Adam_
,
2022-02-23 21:39:22
,
所有人可见
,
阅读 120
菜鸡用java写一个朴素Prim
//朴素的prim
//因为被完爆hhhhhhhhh
import java.util.*;
class Main {
public static void main(String[] args) {
//处理读入
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[][] mat = new int[n + 1][n + 1];
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
mat[i][j] = in.nextInt();
//初始化对应的Prim的维护变量
int[] lc = new int[n + 1];
boolean[] vis = new boolean[n + 1];
Arrays.fill(lc, 0x7fffffff);
lc[1] = 0;
//注意需要迭代N次
int ans = 0;
// boolean flag = true;
for(int i = 1; i <= n; ++i) {
int t = -1;
for(int j = 1; j <= n; ++j)
//必须把vis放到前面,否则会访问到前面的点
if(!vis[j] && (t == -1 || lc[j] < lc[t]))
t = j;
// if(lc[t] == 0x7fffffff) {
// flag = false;
// break;
// }
vis[t] = true;
ans += lc[t];
for(int j = 1; j <= n; ++j)
lc[j] = Math.min(lc[j], mat[j][t]);
}
System.out.println(ans);
}
}