比赛 |
练习赛 |
评测结果 |
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;
}