记录编号	549749	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	ZooxTark➲	是否通过	通过
代码语言	C++	运行时间	0.396 s
提交时间	2020-02-22 16:06:57	内存使用	15.07 MiB

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int n,m;
struct tagEnemy
{
    int x,y,l;
}enemy[100002];
class UnionFindSet
{
private:
    int Maxn;
    int MainSet[100001];
public:
    int FindRoot(int Number)
    {
        return  MainSet[Number] = ((MainSet[Number] == Number)? Number : FindRoot(MainSet[Number]));
    }
    void Reset(int Number)
    {
        Maxn = Number;
        memset(MainSet,0,sizeof(MainSet));
        for(int i = 0;i < Number;i++)
        {
            MainSet[i] = i;
        }
        Number = Number * 2;
        for(int i = 0;i < Number;i++)
        {
            MainSet[i] = i;
        }
    }
    void Union(int num1,int num2)
    {
        MainSet[FindRoot(num1)] = FindRoot(num2 + n);
        MainSet[FindRoot(num2)] = FindRoot(num1 + n);
    }
    bool Relation(int num1,int num2)
    {
        return FindRoot(num1) == FindRoot(num2);
    }
};

bool cmp(tagEnemy a,tagEnemy b)
{
    return a.l > b.l;
}

int main()
{
    freopen("prison1.in","r",stdin);
    freopen("prison1.out","w",stdout);
    UnionFindSet UFS;
    cin >> n >> m;
    UFS.Reset(n);
    for(int i = 1;i <= m;i++)
    {
        cin >> enemy[i].x >> enemy[i].y >> enemy[i].l;
    }
    sort(&enemy[1],&enemy[m + 1],cmp);
    for(int i = 1;i <= m;i++)
    {
        if(UFS.FindRoot(enemy[i].x) == UFS.FindRoot(enemy[i].y))
        {
            cout << enemy[i].l;
            return 0;
        }
        UFS.Union(enemy[i].x,enemy[i].y);
    }
    cout << 0;
    return 0;
}