原题戳这里

关于这道题，本菜狗在阅读各位大佬的题解后终于大彻大悟，顺利ac，在此先感谢各位大佬的题解。 根据题目要求，我们需要将囚犯产生的冲突的影响力的最大值降到最小，这里有那么点贪心和二分答案的味道。这道题的标签是并查集，那么该如何使用并查集求解呢？

我们首先将冲突的情况保存在结构体数组里，并将其从大到小排序，再进行逐个处理。当我们处理每一次冲突时，它都是当前剩余为处理冲突的影响力最大值。若当前冲突的两位囚犯可以分开，那么冲突就被避免，反之，两位囚犯无法分开，那么该次冲突的影响力即为所有产生的冲突的最大值（更大的已经被避免了）。

如何判断会产生冲突的囚犯能否被分开，这里我们用到了并查集。举一个栗子：对于某一对产生冲突的囚犯a、b，a，b互相视对方为敌人，本着敌人的敌人可以成为敌人的原则，我们安排b与a的敌人们关押在一起，b与a的敌人们关押在一起（也就是并查集里面的合并步骤），这样便能避免这次冲突。当然，如果我们发现a、b（a、b分别在之前与其他人存在冲突，已经被安排了）已经住在一起了，那对不起了，a、b只能干架了，这里体现的就是并查集的查找步骤，查看a,b是否在同一个集合（监狱）里。由于之前已经按照冲突的影响力降序排序了，本次冲突即为影响力最大值，也就是答案。

以下是代码：

using namespace std;
typedef long long ll;
typedef pair<int ,int >  PII;
const int N = 2e5+5 , mod = 998244353 , INF = 1e9;

int n,m;
int pre[N];//存放父节点
int enemy[N];//用于记录某个囚犯的敌人
struct conflict{//用于记录冲突情况的结构体
    int a,b;
    ll c;
}x[N];


void init()//初始化
{
    for(int i=1;i<=n;i++)
    {
        pre[i]=i;
    }
}
 

int find(int x)//查找+路径压缩
{
    if(pre[x]==x) return x;
    else return pre[x]=find(pre[x]);

}

void join(int x,int y)//合并
{
    int fx=find(x),fy=find(y);
    if(fx==fy) return ;
    else{
        pre[fx]=fy;
    }

}

bool cmp(conflict r1,conflict r2)
{
    return(r1.c>r2.c);
}

void solve()
{
    cin>>n>>m;
    init();//初始化
    for(int i=1;i<=m;i++)
    {
        cin>>x[i].a>>x[i].b>>x[i].c;
    }
    sort(x+1,x+m+1,cmp);//将影响力从大到小排序
    for(int i=1;i<=m;i++)
    {
        if(find(x[i].a)==find(x[i].b))// 冲突不可避免(a、b已经住在一起了)
        {
            //由于已经将影响力降序排序了，此时冲突产生的影响力即为最大值
            cout<< x[i].c<<"\n";
            return;
        }
        //下面讨论冲突可以避免的情况
        //分开讨论两个囚犯的情况
        //若囚犯a当前没有敌人，那么b就是他的敌人，用数组enemy保存
        if(!enemy[x[i].a]) enemy[x[i].a]=x[i].b;
        //若囚犯a之前已经存在敌人，那么本着敌人的敌人可以是朋友的原则，我们将a之前的敌人与新敌人b合并(关在一起)
        else join(enemy[x[i].a],x[i].b);

        //囚犯b的处理同理 
        if(!enemy[x[i].b]) enemy[x[i].b]=x[i].a; 
        else join(enemy[x[i].b],x[i].a);
    }
    //若循环结束，说明冲突均可避免
    cout<<"0"<<"\n";
    return;
}

int main(){
   	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int t;
   // cin>>t;
	t=1; 
	while(t--)
    {
       solve(); 
    }
    
	return 0;
}