题目链接：https://vjudge.net/contest/123674#problem/G
这题和上一道题差不多，还更简单点，直接用prim算法就行，直接贴AC代码：
1 import java.io.BufferedInputStream; 2 import java.util.Scanner; 3 4 public class Main { 5 final static int N = 1 << 20; 6 static int n, m, a[][] = new int[105][105], b[] = new int[105], sum; 7 8 public static void main(String[] args) { 9 Scanner s = new Scanner(new BufferedInputStream(System.in)); 10 int u, v, w, i, j; 11 while (s.hasNext()) { 12 n = s.nextInt(); 13 if (n == 0) 14 break; 15 16 for (i = 1; i <= n; i++) 17 for (j = 1; j <= n; j++) 18 a[i][j] = 0; 19 m = n * (n - 1) / 2; 20 while (m-- > 0) { 21 u = s.nextInt(); 22 v = s.nextInt(); 23 w = s.nextInt(); 24 a[u][v] = a[v][u] = w; 25 } 26 sum = 0; 27 28 prim(1); 29 System.out.println(sum); 30 } 31 s.close(); 32 } 33 34 static void prim(int u) { 35 int i, j, min, v; 36 for (i = 1; i <= n; i++) { 37 b[i] = a[u][i]; 38 } 39 sum = 0; 40 b[u] = -1; 41 for (i = 1; i <= n; i++) { 42 min = N; 43 v = -1; 44 for (j = 1; j <= n; j++) { 45 if (b[j] != -1 && b[j] < min) { 46 v = j; 47 min = b[j]; 48 } 49 } 50 if (v != -1) { 51 sum += b[v]; 52 b[v] = -1; 53 for (j = 1; j <= n; j++) { 54 if (b[j] != -1 && a[v][j] < b[j]) 55 b[j] = a[v][j]; 56 } 57 } 58 } 59 60 } 61 62 }