```cpp
#include <bits/stdc++.h>
using namespace std;
const int M = 1000100;
int n,m,ans,cnt;
bool vis[M];
struct op {
int op_vlu,op_to;
op(int a,int b) {
op_vlu = a , op_to = b;
}
friend bool operator < (const op &aa,const op &bb) {
return aa.op_vlu > bb.op_vlu;
}
};
struct node {
int to,vlu;
};
vector<node> adj[M];
priority_queue <op> stk;
void insert_edge(int u,int v,int w) {
node pll;
pll.vlu = w;
pll.to = v;
adj[u].push_back(pll);
}
void put_stk(int x) {
cnt++;//
vis[x] = 1;
for(int i=0; i<adj[x].size(); ++i) {
int xv = adj[x][i].to,xw = adj[x][i].vlu;
if(!vis[xv]) stk.push(op(xw,xv));
}
}
int pop_stk() {
int pop_temp = 0,push_temp = 0;
while(vis[stk.top().op_to] && !stk.empty()) stk.pop();
if(!stk.empty()) {
pop_temp = stk.top().op_vlu;
push_temp = stk.top().op_to;
stk.pop();
put_stk(push_temp);
// cnt++;// 为什么不能在这cnt++,因为第一个点加不上去，在这写需要让cnt=1
// put_stk(stk.top().op_to); 不能这样写，改变了堆的结构
// stk.pop();
}
return pop_temp;
}
void prim(int x) {
put_stk(x);
while(!stk.empty() && cnt <= n) {
ans += pop_stk();
// cnt++;//
/*
如果你在pop_stk()中调用cnt++，那么可能会出现以下情况：
你从优先队列中选择了一条边，并尝试将其对应的节点加入到生成树中。
但是，由于某种原因（例如，该节点已经是一个环的一部分，或者该边与
之前的某条边形成了更小的权重），你实际上并没有将这个节点加入到生
成树中（即没有调用put_stk(push_temp);）。
然而，由于你在pop_stk()中递增了cnt，你已经错误地表示了这个节点已
经被加入到生成树中。
这会导致cnt的值比实际加入到生成树中的节点数量要大，进而可能导致算法在
错误的时间点终止（即当cnt > n时），从而得到一个不完整的最小生成树（或
者根本没有找到最小生成树）。
因此，为了确保cnt正确地表示了已经加入到最小生成树中的节点数量，你应该
在将节点加入到生成树中（即调用put_stk(x)）时递增cnt，而不是在选择边（
即调用pop_stk()）时递增。
*/
}
}
int main() {
cin>>n>>m;
int u,v,w;
for(int i=1; i<=m; i++) {
scanf("%d %d %d",&u,&v,&w);
insert_edge(u,v,w);
insert_edge(v,u,w);
}
memset(vis,0,sizeof(vis));
prim(1);
if(cnt == n) cout<<ans;
else cout<<"orz";
return 0;
}
```
by NirvanaCeleste @ 2024-06-12 11:56:49
已结
by NirvanaCeleste @ 2024-06-12 11:57:10