社区讨论

16分求调

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

讨论操作

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

当前回复
10 条
当前快照
1 份
快照标识符
@mjin6g27
此快照首次捕获于
2025/12/23 21:49
2 个月前
此快照最后确认于
2025/12/26 17:50
2 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
struct Edge{
    int u,v,val;
};
vector<Edge> edges;
int ufs[N];
int Find(int x){
    if(ufs[x]<0)return x;
    return ufs[x]=Find(ufs[x]);
}
void Union(int x,int y)
{
    x=Find(x);
    y=Find(y);
    if(x==y)return;
    ufs[x]+=ufs[y];
    ufs[y]=x;
}
int main(){
    memset(ufs,-1,sizeof ufs);
    int cnt=0,sum=0,total=0;
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int u,v,val;
        cin>>u>>v>>val;
        edges.push_back({u,v,val});
        total+=val;
    }
    sort(edges.begin(),edges.end(),[](const Edge& e1,const Edge& e2){
        return e1.val<e2.val;
    });
    for(auto e:edges)
    {
        if(cnt>=n-1)break;
        if(Find(e.u)==Find(e.v))continue;
        sum+=e.val;
        Union(e.u,e.v);
        cnt++;
    }
    if(cnt==n-1)cout<<total-sum;
    else cout<<"orz";
    return 0;
}
(怀疑只对了一个输出orz的点)

回复

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

正在加载回复...