带权并查集，其实这种并查集的核心就是“向量”
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 using namespace std; 5 int n,m,p[20001],r[20001]; //0表示在同一监狱，1表示在不同监狱 6 struct node{ 7 int a,b,c; 8 }d[100000]; 9 int cmp(node x,node y){ 10 return x.c>y.c; 11 } 12 int findp(int x){ 13 if(p[x]!=x){ 14 int px=findp(p[x]); //找到真正的根结点 15 r[x]=(r[p[x]]+r[x])%2; //更新当前结点x和真正根结点px的关系r[x]，括号里的r[x]是和旧的父结点的关系 16 p[x]=px; 17 } 18 return p[x]; 19 } 20 int main() 21 { 22 int ok=0; 23 scanf("%d%d",&n,&m); 24 for(int i=1;i<=n;i++) p[i]=i; 25 for(int i=0;i<m;i++) 26 scanf("%d%d%d",&d[i].a,&d[i].b,&d[i].c); 27 sort(d,d+m,cmp); 28 for(int i=0;i<m;i++){ 29 int x=d[i].a,y=d[i].b,z=d[i].c; 30 int px=findp(x),py=findp(y); 31 if(px!=py){ //两者不在同一集合，需要把x,y放在不同监狱，也就是向量(x,y)为1 32 p[px]=py; //据此可以算出(px,py)的值，也就是r[px] 33 r[px]=(1+r[y]-r[x])%2; 34 } 35 else{ 36 if(!((r[y]-r[x]+2)%2)){ //根据向量关系，两者在同一个监狱 37 ok=1; 38 printf("%d",z); 39 break; 40 } 41 } 42 } 43 if(!ok) printf("0"); 44 return 0; 45 }