标签秩下的文章 - xiaoeyv Blog

登录

找到 2 篇与秩相关的结果

【洛谷】P1892 [BalticOI 2003] 团伙

【洛谷】P1892 [BalticOI 2003] 团伙题目链接：[P1892 [BalticOI 2003] 团伙](https://www.luogu.com.cn/problem/P1892) 思路除了并查集外，还要记录每个人之间的关系，典型的扩展域并查集模板题。代码写的时候用了秩优化，能优化一些效率。 // // Created by xiaoeyv on 2025/6/19. // #define maxn 1010 #define maxm 5010 #include<bits/stdc++.h> using namespace std; int n, m; int pre[maxn * 2], r[maxn * 2]; int find(int x) { return pre[x] == x ? x : pre[x] = find(pre[x]); } void join(int x, int y) { int rx = find(x), ry = find(y); if (rx == ry) return; if (r[rx] < r[ry]) pre[rx] = ry; else { pre[ry] = rx; if (r[rx] == r[ry]) r[rx]++; } } int main() { cin >> n >> m; memset(r, 0, sizeof(r)); for (int i = 1; i <= n * 2; i++) { pre[i] = i; } for (int i = 1; i <= m; i++) { char op; int p, q; cin >> op >> p >> q; if (op == 'F') { join(p, q); } else { join(p + n, q); join(p, q + n); } } set<int> ans; for (int i = 1; i <= n; i++) { ans.insert(find(i)); } cout << ans.size() << endl; return 0; }

C++# C++# 并查集 # 扩展域并查集 # BalticOI # 洛谷 # 秩

xiaoeyv 1年前

0 26 0

【洛谷】P2820 局域网题目链接：P2820 局域网 - 洛谷题目简述去除 $k$ 个边中的最大回路边。思路在输入的时候统计权重总和，减去最小生成树的总和。这道题用简单数组实现 Prim，复杂度是 $O(n^2)$；用堆优化的 Prim 是 $O(k\log n)$； Kruskal 则是 $O(k\log k)\approx O(k\log n)$。在本题规模下（$n\le100$、最坏 $k\approx4950$），这两种算法都可以解决，但Kruskal+并查集更加直观简洁。代码 // // Created by xiaoeyv on 2025/6/19. // #define maxn 110 #define maxm (maxn * (maxn-1))/2 #include<bits/stdc++.h> using namespace std; int pre[maxn], r[maxn], sz[maxn]; bool vis[maxn]; int n, k; int cnt = 0; int ans = 0; struct Edge { int u, v, w; } e[maxm]; int find(int x) { return pre[x] == x ? x : find(pre[x]); } void join(int x, int y) { int rx = find(x), ry = find(y); if ( rx == ry ) return; if ( r[rx] < r[ry] ) pre[rx] = ry; else { pre[ry] = rx; if ( r[rx] == r[ry] ) r[rx]++; } } int main() { cin >> n >> k; memset(r, 0, sizeof(r)); memset(sz, 0, sizeof(sz)); for (int i = 0; i <= n; i++) pre[i] = i; for (int i = 1; i <= k; i++) { int u, v, w; cin >> u >> v >> w; ans += w; e[i].u = u, e[i].v = v, e[i].w = w; } sort(e + 1, e + k + 1, [](const auto &x, const auto &y) { return x.w < y.w; }); for (int i = 1; i <= k && cnt < n - 1; i++) { int u = e[i].u, v = e[i].v, w = e[i].w; int ru = find(u), rv = find(v); if (ru != rv) { join(u, v); ans -= w; cnt++; } } cout << ans << endl; return 0; }

洛谷 C++# C++# 并查集 # 最小生成树 # Kruskal # 洛谷 # 秩

xiaoeyv 1年前

0 21 0