社区讨论

kruskal全wa,求指正

P3366【模板】最小生成树参与者 6已保存回复 21

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
21 条
当前快照
1 份
快照标识符
@mi6vvw94
此快照首次捕获于
2025/11/20 11:40
4 个月前
此快照最后确认于
2025/11/20 16:04
4 个月前
查看原帖
样例对的,下载的一个测试数据也是对的,想不明白问题出在哪
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 5010
#define maxm 200010
inline int read(){
    int x = 0; char c = getchar();
    while(c>'<'||c>'9') c=getchar();
    while(c>='0'&&c<='9'){
        x = (x<<3)+(x<<1)+(c-'0');
        c = getchar();
    }
    return x;
}
int n,m;

struct edge{
    int u,v,w;
    bool operator< (const edge &a) const{
        return w<a.w;
    }
}e[maxm];
int cnt = 0;
inline void addedge(int u,int v,int w){e[++cnt].u = u; e[cnt].v = v; e[cnt].w = w;}
//___________并查集_____________________
struct bingchaji{
    int fa[maxn],size[maxn];
    void ini(){for(int i = 1; i <= n; i++) fa[i] = i;}
    inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
    inline void hebing(int x,int y){
        x = find(x); y = find(y);
        if(x == y) return;
        if(size[y] > size[x]) swap(x,y);
        size[x]+=size[y];
        fa[y]=x;
    }
}b;

int main(){
    n = read(); m = read();
    for(int i = 0; i < m; i++){
        int u=read(),v=read(),w=read();
        addedge(u,v,w);
    }
    b.ini();sort(e+1,e+m+1);
    
    int k = 0,tot = 0;
    for(int i = 1; i <= m; i++){
        if(b.find(e[i].u) != b.find(e[i].v)){
            b.hebing(e[i].u,e[i].v);
            tot+=e[i].w;
            k++;
        }
        if(k == n-1) break;
    }
    
    if(k!=n-1) cout<<"orz"<<endl;
    else cout<<tot<<endl;
    return 0;
}

回复

21 条回复,欢迎继续交流。

正在加载回复...