不知道为什么发在讨论版没人看就发在这里试试

原题：关押罪犯

我的思路：

开一个n*2的并查集，分为区间 1~n 与区间 n+1~2n ，合并在相同区间表示在同一监狱，不同区间表示是敌人。

把输入数据按怨气值从大到小排序，然后开始处理数据；这样可以尽量把怨气值高的犯人分到两个监狱中。

若发现有两个罪犯x和y，在之前已被划分为同一监狱，又在接下来的数据处理中发现他俩有矛盾，则冲突不可避免 ，直接输出；

若所有矛盾都可避免，则输出0

（不知道思路有什么问题......qwq）

代码如下：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;

struct pt{
    int x,y,v;
}p[50020];//存输入 
int j[100020];//非常大的并查集（但不知道为啥RE了两个点） 
bool cmp(pt a,pt b)
{
    return a.v>b.v;
}
int find(int x)
{
    if(x!=j[x])j[x]=find(j[x]);
    return j[x];
}
void _union(int x,int y)
{
    j[find(x)]=find(y);
}
int read()
{
    int num=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while('0'<=c&&c<='9')num=num*10+c-'0',c=getchar();
    return num;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n*2;i++)j[i]=i;//初始化 
    for(int i=1;i<=m;i++){
        p[i].x=read(),p[i].y=read(),p[i].v=read();
    }

    sort(p+1,p+1+n,cmp);

    for(int i=1;i<=m;i++)
    {
        if(find(p[i].x) == find(p[i].y)){//若发现x、y已在一个监狱内（且x、y有矛盾，即冲突不可避免） 
            printf("%d", p[i].v);//输出 
            return 0;
        }

        _union(p[i].x, p[i].y+n);//将x的敌人标记为y，即将x与y放在不同监狱中 
        _union(p[i].y, p[i].x+n);//将y的敌人标记为x，同理 

    }
    printf("0");
    return 0;
}

求大佬指教！QwQ