社区讨论

用kruskal86分,还re了1个点,为啥啊各位大佬

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

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@lo8e0q0c
此快照首次捕获于
2023/10/27 17:04
2 年前
此快照最后确认于
2023/10/27 17:04
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;

struct code{
    long long int a,b;
    long long int d;
};

bool dx(code a,code b){
    return a.d<=b.d;
}

int find(int x,int f[])
{
    if(f[x]==x){
        return x;
    }
    else return find(f[x],f);
}

int main()
{
    long long int n,m,i,s=0,ans=0,x,y;
    cin>>n>>m;
    code a[m];
    int f[n+1];
    for(i=1;i<=n;i++) f[i]=i;
    i=0;
    while(i!=m){
        cin>>a[i].a>>a[i].b>>a[i].d;
        if(a[i].a==a[i].b){
            m--;
            continue;
        }
        i++;
    }
    sort(a,a+m,dx);
    for(i=0;i<m;i++){
        x=find(a[i].a,f);y=find(a[i].b,f);
        if(x==y) continue;
        ans+=a[i].d;s++;
        if(s==n-1) break;
        f[y]=x;
    }
    if(s!=n-1) cout<<"orz";
    else cout<<ans;
    cin>>n;
}

回复

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

正在加载回复...