洛谷P1111 修复公路10分求大亻老帮助

Question

洛谷P1111 修复公路只过了样例和第一个点,求大亻老指点

#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){
    if(b[x]!=x&&b[y]!=y){
        b[max(cha(x),cha(y))]=min(cha(x),cha(y));
        s[min(cha(x),cha(y))]+=s[max(cha(x),cha(y))];
    }
    else
    if(b[x]!=x&&b[y]==y){
        b[y]=cha(x);
        b[y]+=1;
    }
    else
    if(b[x]==x&&b[y]!=y){
        b[x]=cha(y);
        b[x]+=1;
    }
    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=max(ans,X[i].t);
        //cout<<"X[i].t:"<<X[i].t<<endl;
        cun(X[i].x,X[i].y);
        //cout<<"cha(X[i].x):"<<cha(X[i].x)<<endl;
        //cout<<"s[cha(X[i].x)]:"<<s[cha(X[i].x)]<<endl;
        //cout<<"ans:"<<ans<<endl;
       if(s[cha(X[i].x)]>=N){
            cout<<ans;
            return 0;
        }
    }
    cout<<-1;
    return 0;
}

Answer 1

看起来你的代码试图使用 Kruskal 算法来解决这个问题，但是合并集合的方法实现有些问题。在 "cun" 函数中，你需要检查集合的根节点是否相同，而不是简单地比较 b[x] 和 x 是否相等。

改进你的 "cun" 函数，用下面的代码代替你现有的代码：

void cun(long long x, long long y){
    long long fx = cha(x);
    long long fy = cha(y);
    if(fx != fy){
        b[fx] = fy;
        s[fy] += s[fx];
    }
}

在这个修复后的 "cun" 函数中，我们首先找到 x 和 y 的根节点 fx 和 fy，然后只有当 fx != fy 时（即 x 和 y 不在同一集合时）才进行合并，把 x 的根节点 fx 指向 y 的根节点 fy，并更新 fy 的大小。

这个改进应该能帮助你的代码通过更多的测试。