并查集(用pair)

#include <cstdio>
#include <algorithm>

using namespace std;

int s[40005];
pair <int, pair<int, int> > e[100005];
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].second.first, &e[i].second.second, &e[i].first);
}

sort(e + 1,e + m + 1);

for(int i = m; i >= 1; --i){
pair<int, int> &p = e[i].second;
x = find(p.first);
y = find(p.second);
if(x == y){
printf("%d\n", e[i].first);
return 0;
}else{
s[x] = find(n + p.second);
s[y] = find(n + p.first);
}
}

printf("0\n");

return 0;
}

0 条评论

目前还没有评论...

信息

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