1 条题解
-
1昌孝阳 (changxiaoyang) LV 10 @ 2023-9-30 13:22:38
这么简单的题怎么能没题解呢
#include <cstdio> #include <algorithm> #include <iostream> using namespace std; int n, m, f[40001], vis[40001], x, y, z; struct data { int a, b, c; } e[100001]; int comp(data a, data b) { return a.c > b.c; } int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); } int main() { cin >> n >> m; for (int i = 1; i <= m; i++) cin >> e[i].a >> e[i].b >> e[i].c; for (int i = 1; i <= n; i++) f[i] = i; sort(e + 1, e + m + 1, comp); for (int i = 1; i <= m; i++) { x = find(e[i].a); y = find(e[i].b); if (x == y) { cout << e[i].c; return 0; } else { if (vis[e[i].a]) { z = find(vis[e[i].a]); f[y] = z; } else vis[e[i].a] = e[i].b; if (vis[e[i].b]) { z = find(vis[e[i].b]); f[x] = z; } else vis[e[i].b] = e[i].a; } } cout << 0; return 0; }
- 1
信息
- ID
- 168
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 5
- 标签
- 递交数
- 40
- 已通过
- 17
- 上传者