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

洛谷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;
}

看起来你的代码试图使用 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 的大小。

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

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int T,road,root[100005];
struct node{
    int u,v,t;
} item[100005];
bool cmp(node a,node b){
    return a.t<b.t;
}
int find_root(int x){
    if(root[x]==x) return x;
    else return root[x]=find_root(root[x]);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) root[i]=i;
    for(int i=1;i<=m;i++){
        cin>>item[i].u>>item[i].v>>item[i].t;
    }
    sort(item+1,item+m+1,cmp);
    for(int i=1;i<=m;i++){
        int a=item[i].u;
        int b=item[i].v;
        int c=item[i].t;
        T=c;    //更新当前时间
        int A=find_root(a);
        int B=find_root(b);
        if(A==B) continue;
        else{
            root[B]=A;
            road++;  //树的边数+1
        }
        if(road==n-1){  //此时成为连通图
            cout<<T;
            break;
        }
    }
    if(road!=n-1){   //若循环结束后仍不是连通图
        cout<<-1;
    }
    return 0;
}