比赛 练习赛 评测结果 AAAAAAAAAA
题目名称 关押罪犯 最终得分 100
用户昵称 gsj.cpp 运行时间 0.130 s
代码语言 C++ 内存使用 15.26 MiB
提交时间 2019-05-22 14:20:54
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x*f;
}
int n,m,fa[20005],b[100005];
struct qwq
{
	int x,y,w;
}a[100005];
int getf(int x)
{
	if(fa[x]==x)return x;
    fa[x]=getf(fa[x]);
	return fa[x];
}
bool judge(int x,int y)
{
	if(getf(x)==getf(y))return true;
	else return false;
}
bool cmp(qwq a,qwq b)
{
	return a.w>b.w; 
}
int add(int x,int y)
{
	x=getf(fa[x]);
	fa[x]=getf(fa[y]);
}
int main()
{
	freopen("prison1.in","r",stdin);
	freopen("prison1.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=m;i++)a[i].x=read(),a[i].y=read(),a[i].w=read();
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m+1;i++)
	{
		if(judge(a[i].x,a[i].y))
		{
			cout<<a[i].w<<' ';
			break;
		}
		else 
		{
			if(!b[a[i].x])b[a[i].x]=a[i].y;
			else add(b[a[i].x],a[i].y);
			if(!b[a[i].y])b[a[i].y]=a[i].x;
			else add(b[a[i].y],a[i].x);
		}
	}
	return 0;
}