WA求助
  • 板块P1111 修复公路
  • 楼主ln001
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/6/6 13:45
  • 上次更新2023/10/23 13:50:36
查看原帖
WA求助
644963
ln001楼主2023/6/6 13:45

刚学了并查集,不知道为什么不对,求大佬帮助

#include<bits/stdc++.h>
using namespace std;
long long N,M;
long long b[1002],s[1002];
struct XX{
    long long x;
    long long y;
    long long t;
};
bool cmp(XX x,XX y){
	return x.t<y.t;
}
long long cha(long long x){
    if(b[x]==x){
        return x;
    }
    return b[x]=cha(b[x]);
}
bool pan(long long x,long long y){
    return cha(x)==cha(y);
}
void cun(long long x,long long y){
    b[y]=cha(x);
    s[b[y]]+=s[y];
}
int main(){
    cin>>N>>M;
    XX X[M+1];
    for(long long i=0;i<M;i++){
        cin>>X[i].x>>X[i].y>>X[i].t;
    }
    sort(X,X+M,cmp);
    for(long long i=1;i<=N;i++){
        b[i]=i;
        s[i]=1;
    }
    long long ans=0;
    for(long long i=0;i<M;i++){
        ans+=X[i].t;
        cun(X[i].x,X[i].y);
        if(s[cha(X[i].x)]>=N){
            cout<<ans;
            return 0;
        }
    }
    cout<<-1;
    return 0;
}
2023/6/6 13:45
加载中...