21pts求调(Kruskal)

P3366 【模板】最小生成树

@[My_Xuan](/user/679265) 改两个地方: ``` #include <bits/stdc++.h> using namespace std; int f[5005], n, m, ans, x, y, cnt; struct eg { int u, v, w; } a[200005]; bool cmp (eg a, eg b) { return a.w < b.w; } int find (int x) { if (f[x] != x) return f[x] = find (f[x]);//here return x; } int main ( ) { ios :: sync_with_stdio (0); cin.tie (0); //here cin >> n >> m;for (int i = 1; i <= n; i++) f[i] = i; for (int i = 1; i <= m; i++) cin >> a[i].u >> a[i].v >> a[i].w; sort (a + 1, a + m + 1, cmp); for (int i = 1; i <= m; i++) { x = find (a[i].u), y = find (a[i].v); if (x == y) continue; ans += a[i].w, f[y] = x, cnt++; if (cnt == n - 1) {cout << ans; return 0;} } cout << "orz"; return 0; } ```
by Tryst @ 2023-08-10 23:09:18


|