萌新初学克鲁斯卡尔 WA on #4 求调
查看原帖
萌新初学克鲁斯卡尔 WA on #4 求调
1690315
DPOI楼主2025/7/28 16:50

rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct edge{
    int nxt,to,st,w;
}e[600005];
int f[600005];
int find(int x){
    if (f[x]!=x)f[x]=find(f[x]);
    return f[x];
}
void join(int x,int y){
    int f1=find(x),f2=find(y);
    if (f1!=f2)f[f1]=f2;
}
int hd[600005],tot;
void add(int u,int v,int w){
    e[++tot].to=v;
    e[tot].st=u;
    e[tot].w=w;
    e[tot].nxt=hd[u];
    hd[u]=tot;
}
bool cmp(edge x,edge y){
    return x.w<y.w;
}
signed main(){
    int n,m;cin>>n>>m;
    for (int i=1;i<=m;++i){
        int u,v,w;cin>>u>>v>>w;
        add(u,v,w);add(v,u,w);
    }
    for (int i=1;i<=n;++i){
        f[i]=i;
    }
    sort(e+1,e+tot+1,cmp);
    int cnt=0,ans=-1e9;
    for (int i=1;i<=m;++i){
        if (cnt==n-1)break;
        if (find(e[i].to)!=find(e[i].st)){
            join(e[i].to,e[i].st),cnt++,ans=max(ans,e[i].w);
           // cout<<e[i].to<<" "<<e[i].st<<" "<<ans<<' '<<cnt<<'\n';
        }
    }
    cout<<n-1<<" "<<ans<<'\n';
    
}
2025/7/28 16:50
加载中...