用并查集解决,记下了
#include <iostream> #include <cstring> #include <algorithm> using namespace std; #define MAX 5000 // 端点序号 权 并查集 排序 int u[MAX], v[MAX], w[MAX], p[105], r[MAX]; int n, m, sum; int cmp(const int a, const int b) { return w[a]<w[b]; } int find(int x) { return p[x]==x?x:find(p[x]); } void Kruskal() { int i; for (i=1; i<=n; i++) p[i] = i; for (i=1; i<=m; i++) r[i] = i; sort(r+1, r+m+1, cmp); for (i=1; i<=m; i++) { int t = r[i]; int x = find(u[t]); int y = find(v[t]); if (x!=y) { sum += w[t]; p[x] = y; } } } int main() { int i; while (cin>>n && n) { m = n * (n-1) / 2; sum = 0; for (i=1; i<=m; i++) { scanf("%d%d%d",&u[i], &v[i], &w[i]); } Kruskal(); printf("%d\n", sum); } return 0; }