初始化数组时是不是有问题
by Linear_Function @ 2024-04-24 21:44:14
@[Linear_Function](/user/970052) 好像没有欸
by 南瓜桐 @ 2024-04-24 21:46:29
@南瓜铜
- 使用优先队列 priority_queue 时，需要确保队列中的元素数量不会超过其内存容量，否则可能会导致堆内存溢出。在处理大规模输入时，可能需要考虑使用其他数据结构或手动实现堆以避免此问题。
- 在 Prim 算法中，使用 while(q.size()) 来判断是否还有元素需要处理，但需要确保循环能够正确终止。可能需要调整循环终止条件以防止死循环。
by Linear_Function @ 2024-04-24 21:50:19
@[南瓜桐](/user/439327) 破案了！
我写了另一种相同思路的解法，AC 叻。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5001;
const int maxm = 2e5 + 1;
const int inf = 2147483647;
struct edge {
int to, w, nxt;
};
vector<edge> e[maxn];
int dis[maxn];
bool vis[maxn];
void add_edge(int x, int y, int z) {
e[x].push_back({y, z});
e[y].push_back({x, z});
}
int Prim(int s, int n) {
int res = 0, cnt = 0;
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, s});
while (!pq.empty()) {
if (cnt >= n) break;
int u = pq.top().second, d = pq.top().first; pq.pop();
if (vis[u]) continue;
vis[u] = true;
++cnt; res += d;
for (auto& edge : e[u]) {
int v = edge.to, w = edge.w;
if (!vis[v] && w < dis[v]) {
dis[v] = w;
pq.push({dis[v], v});
}
}
}
return (cnt == n) ? res : -1;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y, z;
cin >> x >> y >> z;
add_edge(x, y, z);
}
int ans = Prim(1, n);
if (ans == -1) cout << "orz" << endl;
else cout << ans << endl;
return 0;
}
```
by Linear_Function @ 2024-04-24 21:55:23
@[南瓜桐](/user/439327)
你的 ```maxm``` 开小了。
by fsdgakjl @ 2024-04-24 21:59:31
@[fsdgakjl](/user/115110) 是的，无向边因该变数乘以二，真的很感谢您
by 南瓜桐 @ 2024-04-24 22:10:44