1 条题解

  • 0
    @ 2024-12-27 19:57:40
    #include<bits/stdc++.h>//2
    using namespace std;
    const int N=100010;
    int f[N];
    struct Node{
        int x,y,t;
    }a[N];
     
    bool cmd(Node a,Node b)
    {
        return a.t<b.t;
    }
     
    int find(int x)
    {
        if(f[x]!=x) f[x]=find(f[x]);
        return f[x];
    }
     
    int main()
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) f[i]=i;
        for(int i=1;i<=m;i++)
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);
        sort(a+1,a+m+1,cmd);
        int cnt=n-1;
        for(int i=1;i<=m;i++)
        {
            int fa=find(a[i].x);
            int fb=find(a[i].y);
            if(fa==fb) continue;
            f[fa]=fb;
            cnt--;
            if(cnt==0)
            {
                printf("%d",a[i].t);
                return 0;
            }
        }
        printf("-1");
        return 0;
    }
    
    • 1

    信息

    ID
    5169
    时间
    1000ms
    内存
    125MiB
    难度
    3
    标签
    递交数
    34
    已通过
    11
    上传者