【带权并查集+贪心】关押罪犯

题意：有n个罪犯，有两个监狱，某些罪犯之间看不顺眼要发生冲突，问你怎么去关押他们才能使得冲突值最小。 分析：并查集，把敌人的敌人分在一起，如果两个罪犯之间没有冲突，那么x罪犯就一定要和y罪犯的敌人祖先关在一起，要是y罪犯没有敌人祖先，那就x成为y罪犯的敌人祖先。反之就合并x到y的敌人集合。同理y也是一样的。但是如果x和y已经在一个集合内的话，此时就不能将他们分开，不然之前的分配规则就会打破。答案输出此时的冲突值。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+12;
const int M=1e5+12; 
int fa[N],n,m,de[N];
struct p{
  int x,y,v;
  int operator <(const p &other)
  {
    return v>other.v;
  }
}a[M];
int fin(int x)
{
  while( x!=fa[x] )
  {fa[x]=fa[fa[x]];
    x=fa[x];
  };
  return x;
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++) fa[i]=i;
  for(int i=1;i<=m;i++)
    cin>>a[i].x>>a[i].y>>a[i].v;
  sort(a+1,a+1+m);
  for(int i=1;i<=m;i++)
  {
    int l=fin(a[i].x),r=fin(a[i].y);
    if( l==r ) {cout<<a[i].v;return 0;}
    if( !de[ l ] ) de[l]=r;
    else fa[r]=de[l];
    if( !de[ r ] ) de[r]=l;
    else fa[l]=de[r];
  }
  cout<<0;

}