题目

https://www.luogu.com.cn/problem/P1525

题解

代码

#include <cstdio>
#include <algorithm>
using namespace std;
int a[20005],b[20005];
struct S
{
    int x,y,data;
} s[1000005];
bool cmp(S a,S b){
    return a.data>b.data;
}
int find(int x){
    if (x!=a[x]){
        a[x]=find(a[x]);
    }
    return a[x];
}
void con(int x,int y){
    x=find(x);
    y=find(y);
    if (x!=y) a[x]=y;
      
}
bool check(int x,int y){
    x=find(x);
    y=find(y);
    if (x!=y) return false;
    else return true;
    
    
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;i++){
        a[i]=i;
    }
    for (int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&s[i].x,&s[i].y,&s[i].data);
    }
    sort(s+1,s+m+1,cmp);
    for (int i=1;i<=m+1;i++){
        if (check(s[i].x,s[i].y)){
            printf("%d",s[i].data);
            break;
        }
        if (!b[s[i].x]) b[s[i].x]=s[i].y;
        else con(b[s[i].x],s[i].y);

        if (!b[s[i].y]) b[s[i].y]=s[i].x;
        else con(b[s[i].y],s[i].x);
    }
    return 0;
}

解析

没怎么用过c++，除了头文件和排序，其他和c一模一样

这道题是并查集，首先对罪犯之间的仇恨排序，再从大至小检查，优先让仇恨值大的罪犯分开，并且用b数组记录下对方的序号，

等继续遍历到同一个罪犯，根据敌人的敌人和自己在一个监狱的规律合并。最后检查到两罪犯在一个监狱，则输出他们的仇恨值。