洛谷 P1525 关押罪犯

你好，我又来水并查集了。等待二分图的请离开。（日后会补上的，但现在没有）

至于我为什么把标签打上二分图》》》那只是一种做法啦

---

 

极度朴素的并查集啊 （虽然还有个排序的说）。毕竟是普及+/提高的题 啊。

放代码（不懂看看代码就懂了 逃】）

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,fa[20001],dr[20001];
struct ss{
    int a,b;
    long long c;
}ch[100001];
int cmp(ss a,ss b) {
    return a.c>b.c;
}
int fi(int k)
{
    if(fa[k]==k)return k;
    else return fa[k]=fi(fa[k]);
}
int main()
{
    //freopen("1.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d%lld",&ch[i].a,&ch[i].b,&ch[i].c);
    sort(ch+1,ch+m+1,cmp);
    for(int i=1;i<=2*n;i++) fa[i]=i;
    for(int i=1;i<=m;i++) {
        int fx=fi(ch[i].a);
        int fy=fi(ch[i].b);
        if(fx==fy) {
            cout<<ch[i].c<<endl;
            return 0;
        }
        if(!dr[ch[i].a]) dr[ch[i].a]=ch[i].b;
            else fa[fi(dr[ch[i].a])]=fi(ch[i].b);
        if(!dr[ch[i].b]) dr[ch[i].b]=ch[i].a;
            else fa[fi(dr[ch[i].b])]=fi(ch[i].a);
    }
    cout<<"0"<<endl;
    return 0;
}

告辞。