无坑，裸题。直接敲就恩那个AC。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 #include <cctype> 6 #include <algorithm> 7 #include <numeric> 8 9 #define typec int 10 using namespace std; 11 12 const int V = 105; 13 const int inf = 0xffff; 14 int vis[V]; typec lowc[V], Map[V][V]; 15 16 typec prim (typec cost[][V], int n) { 17 int i, j, p; 18 typec minc, res = 0; 19 memset(vis, 0, sizeof(vis)); 20 vis[0] = 1; 21 for (int i = 1; i < n; ++ i) lowc[i] = cost[0][i]; 22 for (int i = 1; i < n; ++ i) { 23 minc = inf; p = -1; 24 for (j = 0; j < n; ++ j) { 25 if (0 == vis[j] && minc > lowc[j]) { 26 minc = lowc[j]; p = j; 27 } 28 } 29 if (inf == minc) return -1; 30 res += minc; vis[p] = 1; 31 for (j = 0; j < n; ++ j) { 32 if (0 == vis[j] && lowc[j] > cost[p][j]) 33 lowc[j] = cost[p][j]; 34 } 35 } 36 return res; 37 } 38 39 int main () { 40 int n; 41 while (~scanf("%d", &n) && n) { 42 for (int i = 0; i < V; ++ i) { 43 for (int j = 0; j < V; ++ j) { 44 if (i == j) Map[i][j] = 0; 45 else Map[i][j] = inf; 46 } 47 } 48 for (int i = 0; i < n * (n - 1) / 2; ++i) { 49 int x, y, c; scanf("%d%d%d", &x, &y, &c); 50 if (x == y) continue; 51 Map[x - 1][y - 1] = Map[y - 1][x - 1] = min(Map[x - 1][y - 1], c); 52 } 53 cout << prim(Map, n) << endl; 54 } 55 return 0; 56 }