记录编号	588576	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.110 s
提交时间	2024-06-06 12:12:33	内存使用	2.81 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct gc{
    int x,y,w; 
}a[100010]; 
int n,m,f[20010],d[20010]; 
bool cmp(gc x,gc y)
{
    return x.w>y.w;
}
int find(int x)
{
    if(f[x]==x)
    {
        return x;
    }
    else
    {
        return f[x]=find(f[x]);
    }
}
void un(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
    {
        f[fx]=fy;
    }
}
int main()
{
    freopen("prison1.in","r",stdin);
    freopen("prison1.out","w",stdout);
    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].w);
    }
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(find(a[i].x)==find(a[i].y))
        {
            printf("%d",a[i].w);
            return 0;
        }
        else
        {
            if(d[a[i].x]==0)
            {
                d[a[i].x]=a[i].y;
            }
            else
            {
                un(d[a[i].x],a[i].y);
            }
            if(d[a[i].y]==0)
            {
                d[a[i].y]=a[i].x;
            }
            else
            {
                un(d[a[i].y],a[i].x);
            }
        }
    }
    printf("0");
    return 0;
}