比赛 练习赛 评测结果 AAAAAAAAAA
题目名称 关押罪犯 最终得分 100
用户昵称 氢氦 运行时间 0.207 s
代码语言 C++ 内存使用 15.57 MiB
提交时间 2019-05-21 20:31:59
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100010

using namespace std;

int fa[maxn],n,m,enemy[maxn];

struct Node{
    int a,b,c;
    //bool operator < (const Node & rhs)const{
    //	return c>rhs.c;
    //}
}node[maxn];

bool cmp(Node x,Node y)
{
    return x.c>y.c;
}

int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

void unionn(int x,int y)
{
    fa[find(x)]=find(y);
}

int main()
{
	freopen("prison1.in","r",stdin);
	freopen("prison1.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    scanf("%d%d%d",&node[i].a,&node[i].b,&node[i].c);
    for(int i=1;i<=n;i++)
    fa[i]=i;
    sort(node+1,node+m+1,cmp);
    for(int i=1;i<=m;i++){
        int x=node[i].a,y=node[i].b;
        if(find(node[i].a)==find(node[i].b)){
            printf("%d\n",node[i].c);
            return 0;
        }	
        if(enemy[x]==0)enemy[x]=y;
        else unionn(enemy[x],y);
        if(enemy[y]==0)enemy[y]=x;
        else unionn(enemy[y],x);
    }
    printf("0\n");
    return 0;
}