[noip2010]关押罪犯 并查集

第一次看的时候想到了并查集,但是不知道怎么实现;

标解,f[i]表示i所属的集合,用f[i+n]表示i所属集合的补集,实现的很巧妙,可以当成一个使用并查集的巧妙应用;

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<ctime>
#include<vector>
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=;
struct node{
int x,y,v;
bool operator<(const node& b)const{return v>b.v;}
}e[];
int f[maxn<<],n,m;
void init(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].v);
sort(e+,e+m+);
}
void print(int x){cout<<x<<endl;exit();}
int getfather(int x){return f[x]==x?x:f[x]=getfather(f[x]);}
void work(){
for(int i=;i<=(n<<);i++)f[i]=i;
int x,y;
for(int i=;i<=m;i++){
x=getfather(e[i].x);y=getfather(e[i].y);
if(x==y)print(e[i].v);
else {f[x]=getfather(e[i].y+n),f[y]=getfather(e[i].x+n);}
}
print();
}
int main(){
init();
work();
}
上一篇:常用排序算法比较与分析


下一篇:记一次 oracle 12.2 RAC : Transaction recovery: lock conflict caught and ignored