1 solutions

  • 0
    @ 2024-10-28 23:06:43

    主要考点:并查集

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    struct data {int x,y,z;};
    data f[100005];
    int n,m,a[20005],b[20005],i;
    bool cmp(data a,data b)
    {
        return a.z>b.z;
    }
    int find(int x)
    {
        if(a[x]==x) return x;
        a[x]=find(a[x]);
        return a[x];
    }
    void ad(int x,int y)
    {
        x=find(a[x]);
        y=find(a[y]);
        a[x]=y;
    }
    bool check(int x,int y)
    {
        x=find(x);
        y=find(y);
        if(x==y) return true;
        return false;
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++) a[i]=i;
        for(i=1;i<=m;i++)
            scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].z);
        sort(f+1,f+m+1,cmp);
        for(i=1;i<=m+1;i++)
        {
            if(check(f[i].x,f[i].y)) {printf("%d",f[i].z);break;}
            else
            {
                if(!b[f[i].x]) b[f[i].x]=f[i].y;
                    else {ad(b[f[i].x],f[i].y);}
                if(!b[f[i].y]) b[f[i].y]=f[i].x;
                    else {ad(b[f[i].y],f[i].x);}
            }
        }
        return 0;
    }
    
    
    
    • 1

    Information

    ID
    6987
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    1
    Tags
    (None)
    # Submissions
    23
    Accepted
    2
    Uploaded By