社区讨论

用kruskal为什么只有28分啊各位大佬,还re了几个点

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

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@lo8ecbh6
此快照首次捕获于
2023/10/27 17:14
2 年前
此快照最后确认于
2023/10/27 17:14
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 main()
{
    long long int n,m,i=0,s=0,ans=0;
    cin>>n>>m;
    code a[m];
    bool w[n+1]={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++){
        if(s==n) break;
        if(w[a[i].a] && w[a[i].b]){
            continue;
        }
        ans+=a[i].d;
        if(!w[a[i].a]){
            w[a[i].a]=1;
            s++;
        }
        if(!w[a[i].b]){
            w[a[i].b]=1;
            s++;
        }
    }
    if(s!=n) cout<<"orz";
    else cout<<ans;
    cin>>n;
}

回复

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

正在加载回复...