焚魂 @ 2024-09-16 15:53:36
感觉不应该啊
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,k,f[5010],mst;
struct node{
int u,v,w;
bool operator < (const node &a) const {
return w > a.w;
}
};
priority_queue<node,vector<node> > q;
node getnode(int u,int v,int w) {
return node{u,v,w};
}
int find(int x) {
if(f[x] != x) f[x] = find(f[x]);
return f[x];
}
void unionn(int x,int y) {
x = find(x);
y = find(y);
f[y] = x;
}
int main() {
cin >> n >> m;
for(int i = 1;i <= m;i++) {
int x,y,z;
cin >> x >> y >> z;
q.push(getnode(x,y,z));
}
for(int i = 1;i <= n;i++) f[i] = i;
while(!q.empty()) {
if(find(q.top().u) != find(q.top().v)) {
k++;
mst += q.top().w;
unionn(q.top().u,q.top().v);
q.pop();
}
if(k == n-1) break;
}
cout << mst;
return 0;
}
by Crab_Tang @ 2024-09-16 16:11:27
@焚魂 wtf?从未见过诶。sort写能过吗
by JOKER_chu @ 2024-09-16 16:13:02
@焚魂 你的 while
里有问题
by Crab_Tang @ 2024-09-16 16:13:08
@焚魂 我知道了,如果top相等也要Pop掉。不能让他留着。
by JOKER_chu @ 2024-09-16 16:14:03
while(!q.empty()) {
if(find(q.top().u) != find(q.top().v)) {
k++;
mst += q.top().w;
unionn(q.top().u,q.top().v);
}
q.pop(); // 这条边不能合并也要弹出
if(k == n-1) break;
}
by 焚魂 @ 2024-09-16 16:14:33
@Crab_Tang sort可以
明白,感谢感谢 @JOKER_chu @Crab_Tang
by 焚魂 @ 2024-09-16 16:17:03
@Crab_Tang 我看测评时间,用这个好像比sort快一丝丝(大概十分之一
by Crab_Tang @ 2024-09-16 18:33:33
@焚魂 一丝丝基本是评测ji的波动啦。再说,你放堆里面还要出堆,存数组里面一次性排好肯定快的