#1 AC,其他 WA
查看原帖
#1 AC,其他 WA
731644
_cyh0412_楼主2022/8/2 19:45
#include<bits/stdc++.h>
using namespace std;

int k[20010],fa[20010];

struct node
{
    int a_j,b_j;
    long long c_j;
}a[100010];

bool comp(node x,node y)
{
    return x.c_j>y.c_j;
}

int find(int z)
{
    if (fa[z]==z) return z;
    return fa[z]=find(fa[z]);
}

int main()
{
    int n,m,f1,f2,i=1;
    cin>>n>>m;
    for (i=1;i<=n;i++)
    {
        fa[i]=i;
        k[i]=-1;
    }
    for (long long x=1;x<=m;x++)
        cin>>a[x].a_j>>a[x].b_j>>a[x].c_j;
    sort(a+1,a+m+1,comp);
    while (1)
    {
        if (find(fa[a[i].a_j])==find(fa[a[i].b_j]))
        {
            cout<<a[i].c_j;
            return 0;
        }
        if (k[a[i].a_j]==-1)
        {
            k[a[i].a_j]=a[i].b_j;
        }
        if (k[a[i].b_j]==-1)
        {
            k[a[i].b_j]=a[i].a_j;
        }
        f1=find(a[i].a_j);
		f2=find(a[i].b_j);
        fa[find(k[f1])]=f2;
        fa[find(k[f2])]=f1;
        i++;
    }
    cout<<"0"<<endl;
    return 0;
}
2022/8/2 19:45
加载中...