题目

分析

这道题和食物链那道题有点像
都是用维护的距离数组表示同类或者相对关系

对怨气值进行排序
如果全部没冲突记得输出0

距离相差为0表示在一个监狱，距离相差为1表示在不同的监狱

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=2e4+7;
int n,m;
int p[N];
ll dist[N];
bool check[N];

vector<pair<ll,pair<int,int>>> vec;

int find(int x)
{
    if(p[x]!=x){
        int t=find(p[x]);
        dist[x]+=dist[p[x]];
        p[x]=t;
    }
    return p[x];
}
int main()
{
    int flag=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;
    //距离为偶数表示一组，距离为奇数表示不同组
    for(int i=0;i<m;i++){
        int a,b;ll c;
        scanf("%d%d%lld",&a,&b,&c);
        vec.push_back({c,{a,b}});
    }
    sort(vec.begin(),vec.end(),greater<pair<ll,pair<int,int>>>());
   /* for(auto i:vec){
        printf("%lld %d %d\n",i.first,i.second.first,i.second.second);
    }*/
    for(auto i:vec){
        ll c=i.first; int a=i.second.first; int b=i.second.second;
        int pa=find(a);int pb=find(b);//先通过find函数找到各自的祖宗节点
        //就两个考虑：不在同一树里，和在同一个树里
        if(pa!=pb){
            p[pb]=pa;
            dist[pb]=dist[a]-dist[b]+1;
        }else{
            if((dist[a]-dist[b])%2==0){
                flag=1;
                printf("%lld\n",c);
                 break;
            }
        }
        /*if(!check[a]&&!check[b]){//两个都是新的
            p[b]=find(a);
            dist[b]=1;//不同类
            check[a]=check[b]=true;
        }else if(check[a]&&check[b]&&find(a)!=find(b)){//两个都是旧的，但是不同集合
            p[find(b)]=find(a);
            dist[find(b)]=dist[a]-dist[b]+1;
        }else if(check[a]!=check[b]){//一新一旧
            int neww,oldd;
            if(!check[a]) neww=a,oldd=b;
            else neww=b,oldd=a;
            p[neww]=find(oldd);
            dist[neww]=dist[oldd]+1;
            check[neww]=true;
        }else if(check[a]&&check[b]&&find(a)==find(b)){//两个都是旧的，并且同一集合
            if((dist[a]-dist[b])%2){
                flag=1;
                printf("%lld\n",c);
                break;
            }
        }*/
    }
    if(flag==0) printf("0\n");
    return 0;
}