洛谷 P1525 关押罪犯

时间:2022-01-15 14:36:37

洛谷 P1525 关押罪犯洛谷 P1525 关押罪犯洛谷 P1525 关押罪犯洛谷 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;
}

告辞。