记录编号	585481	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	超人	是否通过	通过
代码语言	C++	运行时间	0.276 s
提交时间	2023-12-12 20:48:11	内存使用	16.22 MiB

#include<bits/stdc++.h>
using namespace std;
const int M=1e6;
struct prison1
{
    int x,y,z;
};prison1 add[M];
long long n,m,a[M],b[M];
bool centraly(prison1 s,prison1 d)
{
    return s.z>d.z;
}
int income(int x)
{
    if(a[x]==x) return x;
    a[x]=income(a[x]);
    return a[x];
}
void outcome(int x,int y)
{
    x=income(a[x]);
    y=income(a[y]);
    a[x]=y;
}
bool upcome(int x,int y)
{
    x=income(a[x]);
    y=income(a[y]);
    if(x==y) return true;
    else return false;
}
int main()
{
    freopen("prison1.in","r",stdin);
    freopen("prison1.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++) a[i]=i;
    for(int i=1;i<=m;i++) cin>>add[i].x>>add[i].y>>add[i].z;
    sort(add+1,add+m+1,centraly); 
    for(int i=1;i<=m+1;i++)
    {
        if(upcome(add[i].x,add[i].y))
        {
            cout<<add[i].z;
            break;
        }
        else
        {
            if(!b[add[i].x]) b[add[i].x]=add[i].y;
            else outcome(b[add[i].x],add[i].y);
            if(!b[add[i].y]) b[add[i].y]=add[i].x;
            else outcome(b[add[i].y],add[i].x);
        }
    }
    return 0;
}