求出最小生成树,用总的边和 减去 生成树的值
可能存在多个连通块,所以判断d[t] != INF得到当前点是不是连通块的第一个点
(这个点即无边,就不用加到生成树的权值里)
import java.util.*;
public class Main{
static int N = 110, n, m, INF = 0x3f3f3f3f, sum;
static int d[] = new int[N], g[][] = new int[N][N];
static boolean st[] = new boolean[N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for(int i = 0; i < N; i ++){
Arrays.fill(g[i], INF);
}
while(m -- != 0){
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
g[a][b] = g[b][a] = c;
sum += c;
}
System.out.println(prim());
}
static int prim(){
int res = 0;
Arrays.fill(d, INF);
for(int k = 0; k < n; k ++){
int t = 0;
for(int i = 1; i <= n; i ++){
if(!st[i] && d[t] >= d[i]) t = i;
}
st[t] = true;
if(d[t] != INF) res += d[t];
for(int i = 1; i <= n; i ++){
d[i] = Math.min(d[i], g[t][i]);
}
}
return sum - res;
}
}