[codevs 1069 关押罪犯] [NOIP2010提高T3]

传送门http://codevs.cn/problem/1069/
将边从大到小排序，用并查集维护，第一条无法满足的边就是答案。重点在于如何记录哪些点不在同一个集合。我们给每一个实点A对应一个虚点A’。若要记录A、B两点不在同一集合即给A、B’以及B、A’之间连边。接下来，若要记录B、C两点不在同一集合，连边之后A、C就在同一集合了。
就不要吐槽我的图片丑了。。好不容易才画起来的呢。。
贴代码

/* 作者:ymzQwQ 题目:p1069 关押罪犯 */

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=20000,M=100000;
int n,m,f[2*N+10],ans;
struct data{
    int x,y,z;
}a[M+10];

int gf(int x){ return f[x]==x?x:f[x]=gf(f[x]); }

int cmp(const data q,const data w){ return q.z>w.z; }

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n*2;i++) f[i]=i;
    for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=m;i++){
        int fx=gf(a[i].x),fy=gf(a[i].y);
        if (fx==fy){ ans=a[i].z;break; }
         else f[fx]=gf(a[i].y+n),f[fy]=gf(a[i].x+n); 
    }
    printf("%d",ans);
    return 0;
}