luogu#P1525 关押罪犯

题意：

有N个罪犯，将关至2个监狱中。其中，罪犯如果关在同一个监狱，则两两之间存在怨气值c[i]。求第一个怨气值，要求此怨气值最小。

解法：

贪心，先对怨气值从大到小排序，然后将两名罪犯关至不同的监狱。直至存在一对罪犯无法关至不同的监狱（若关至同一监狱，则会和已经关押的罪犯产生怨气，这个值\(>\)当前值，则不是最优），那么此时的怨气值就是答案。

对于并查集的维护

可以开2倍的数组。如x y是有怨气，则Union(x+n,y); Union(x,y+n);

#include<iostream>
#include<algorithm>
using namespace std;;
struct p{int x,y,h;}a[200005];
bool cmp(p x,p y){return x.h>y.h;}
int f[40050];

int fnd(int i);
void uni(int i,int k);
int main()
{
    int i;
    int n,m;
    cin>>n>>m;
    for(i=1;i<=n*2;i++)
        f[i]=i;
    for(i=1;i<=m;i++)
        cin>>a[i].x>>a[i].y>>a[i].h;
    sort(a+1,a+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        if(fnd(a[i].x)==fnd(a[i].y)||fnd(a[i].x+n)==fnd(a[i].y+n))
        {
            cout<<a[i].h;
            return 0;
        }
        uni(a[i].x,a[i].y+n);
        uni(a[i].x+n,a[i].y);
    }
    cout<<"0";
    return 0;
}
int fnd(int i)
{
    if(f[i]==i)
        return i;
    return f[i]=fnd(f[i]);
}
void uni(int i,int k)
{
    if(fnd(i)!=fnd(k))
        f[fnd(i)]=fnd(k);
    return ;
}