用优先队列写kruskal却t了8个点求助

P3366 【模板】最小生成树

焚魂 @ 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的波动啦。再说,你放堆里面还要出堆,存数组里面一次性排好肯定快的


|