找到
8
篇与
C++
相关的结果
- 第 2 页
-
【洛谷】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; }
-
【洛谷】P2078 朋友 题目链接：P2078 朋友 - 洛谷 思路 这道题思路很简单，建立A公司和B公司的并查集，遍历小明认识的人ans1和小红认识的人ansB，然后输出min(ansA, ansB)即可 代码 // // Created by xiaoeyv on 2025/6/18. // #define maxn 10010 #include<bits/stdc++.h> using namespace std; int n, m, p, q; int preA[maxn], rA[maxn], preB[maxn], rB[maxn]; int find(int x, int *pre) { return pre[x] == x ? x : pre[x] = find(pre[x], pre); } void join(int x, int y, int *pre, int *r) { int rx = find(x, pre), ry = find(y, pre); if (rx == ry) return; if (r[rx] < r[ry]) pre[rx] = ry; else { pre[ry] = rx; if (r[rx] == r[ry]) r[rx]++; } } int ansA = 0, ansB = 0; int main() { cin >> n >> m >> p >> q; // init for (int i = 0; i <= n; i++) { preA[i] = i; } for (int i = 0; i <= m; i++) { preB[i] = i; } memset(rA, 0, sizeof(rA)); memset(rB, 0, sizeof(rB)); while (p--) { int x, y; cin >> x >> y; join(x, y, preA, rA); } while (q--) { int x, y; cin >> x >> y; join(-x, -y, preB, rB); } int rootA = find(1, preA); int rootB = find(1, preB); for (int i = 1; i <= n; i++) if (find(i, preA) == rootA) ansA++; for (int i = 1; i <= m; i++) if (find(i, preB) == rootB) ansB++; cout << min(ansA, ansB) << endl; return 0; }
-
Dijkstra C++模板 邻接矩阵（无向图）模板 Dijkstra-邻接矩阵-堆优化.cpp // // Created by xiaoeyv on 2025/6/22. // #define maxn 2510 #define INF 0x3f3f3f3f #include <bits/stdc++.h> using namespace std; int n, m; int dis[maxn], vis[maxn]; int g[maxn][maxn]; int s; int main() { cin >> n >> m; memset(g, 0x3f, sizeof(g)); for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; // 无向图 g[u][v] = g[v][u] = min(g[u][v], w); } // cin >> s; s = 1; memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); dis[s] = 0; for (int i = 1; i <= n; i++) { int minn = INF, minp = -1; for (int j = 1; j <= n; j++) { if (!vis[j] && dis[j] < minn) { minn = dis[j]; minp = j; } } if (minp == -1) break; vis[minp] = 1; for (int j = 1; j <= n; j++) { if (g[minp][j] != INF) { dis[j] = min(dis[j], dis[minp] + g[minp][j]); } } } if (dis[n] == INF) cout << "INF"; else cout << dis[n]; }Dijkstra-邻接表-堆优化 // // Created by xiaoeyv on 2025/6/22. // #define maxn 2510 #define maxm 200010 #include<bits/stdc++.h> using namespace std; int n,m; int dis[maxn], vis[maxn]; vector<pair<int, int>> g[maxn]; int s; int main() { memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); cin>>n>>m; for(int i=0;i<m;i++) { int u,v,w; cin>>u>>v>>w; g[u].emplace_back(v,w); g[v].emplace_back(u,w); } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<> > pq; s = 1; dis[s] = 0; pq.emplace(0,s); while(!pq.empty()) { int u = pq.top().second; pq.pop(); if (vis[u]) continue; vis[u] = 1; for (auto [v, w] : g[u]) { if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; pq.emplace(dis[v], v); } } } if (dis[n] == 0x3f3f3f3f) cout << "INF" << endl; else cout << dis[n] << endl; }Dijkstra-结构体-堆优化 // // Created by xiaoeyv on 2025/6/22. // #define maxn 2510 #define maxm 200010 #define INF 0x3f3f3f3f #include<bits/stdc++.h> using namespace std; int n, m; int dis[maxn], vis[maxn]; struct Edge { int to, w; }; vector<Edge> g[maxm]; int s; int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; // 无向图 g[u].push_back({v, w}); g[v].push_back({u, w}); } // cin >> s; s = 1; memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); dis[s] = 0; priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > q; q.emplace(0, s); while (!q.empty()) { int u = q.top().second; q.pop(); if (vis[u]) continue; vis[u] = 1; for (auto &e: g[u]) { int v = e.to, w = e.w; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; q.emplace(dis[v], v); } } } if (dis[n] == INF) cout << "INF"; else cout << dis[n]; }
