P1525 [NOIP2010 提高组] 关押罪犯 （并查集 扩展域

添加链接描述

#include
using namespace std;
const int N=4e4+9,M=1e5+9;
int fa[N];
struct node {
  int a,b,c;
}t[M];
bool cmp(node a,node b){
  return a.c>b.c;
}
int find(int x){
  if(x==fa[x])return fa[x];
  return fa[x]=find(fa[x]);
}
void merge(int a,int b){

  fa[find(a)]=find(b);
}
int main(){
  int n,m;
  scanf("%d%d",&n,&m);
  for(int i=1;i<=4e4+5;i++){
    fa[i]=i;
  }
  for(int i=1;i<=m;i++){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    t[i]={a,b,c};
  }
  sort(t+1,t+1+m,cmp);
  for(int i=1;i<=m;i++){
    int a=t[i].a,b=t[i].b,c=t[i].c;
    if(find(a)==find(b)||find(a+n)==find(b+n)){
      printf("%d",c);
      return 0;
    }
    else merge(a+n,b),merge(a,b+n);
  } 
  printf("0");

  return 0;
}