并查集

###block code
#include<cstdio>
#include<algorithm>
using namespace std;
int s[20010*2];
struct edge
{
int a,b,c;
bool operator<(const edge&x)
const{
return c<x.c;
}
}e[101000];
int n,m;
int x,y;
int find(int k)
{
return s[k]==k?k:s[k]=find(s[k]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=2*n;i++)s[i]=i;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
sort(e+1,e+m+1);
for(int i=m;i>=1;i--)
{
x=find(e[i].a);
y=find(e[i].b);
if(x==y)
{
printf("%d",e[i].c);
return 0;
}
else
{
s[x]=find(n+e[i].b);
s[y]=find(n+e[i].a);
}
}
printf("0");
return 0;
}

0 条评论

目前还没有评论...

信息

ID
1776
难度
6
分类
图结构 | 二分图 点击显示
标签
递交数
3543
已通过
1015
通过率
29%
被复制
11
上传者