1 条题解
-
0
C++ :
#include <cstdio> #include <algorithm> using namespace std; struct vi { int start; int end; int cost; } edge[5000], et; int p[101]; int Find(int n) { return n == p[n] ? n : p[n] = Find(p[n]); } bool cmp(vi a, vi b) { return a.cost < b.cost; } int main() { int n, m, i, k, sum, flag, ST, EN; while (scanf("%d%d", &n, &m) != EOF, n) { for (i = 1; i <= m; i++) p[i] = i; for (k = i = 0; i < n; i++) { scanf("%d%d%d", &et.start, &et.end, &et.cost); edge[k++] = et; } sort(edge, edge + k, cmp); for (sum = i = 0; i < k; i++) { ST = Find(edge[i].start); EN = Find(edge[i].end); if (ST != EN) { p[ST] = EN; sum += edge[i].cost; } } for (flag = 0, i = 1; i <= m; i++) if (p[i] == i) flag++; if (flag == 1) printf("%d\n", sum); else puts("Error!"); } return 0; }
- 1
信息
- ID
- 1951
- 时间
- 1000ms
- 内存
- 32MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者