题解 | #[NOIP2010]关押罪犯#

借鉴了别人的题解加上自己的理解
1、只有两座监狱，所以两个罪犯要么在同一个监狱要么在不同监狱

2、将影响力从大到小排序，从大到小枚举每个冲突，尽可能的让冲突避免（即将两个人分到不同监狱），直到出现无法避免冲突的情况，因为已经将冲突由大到小排序，之后的冲突都比这个冲突小，所以该冲突就是答案要求的。

3、模拟：按冲突从大到小枚举，假如a和b会产生冲突，为了避免a和b发生冲突，将a和b分到两个不同监狱去。继续枚举，发现a和c会产生冲突，为了避免a和c的冲突，你很自然的会把a和c放到不同监狱里。此时必然有b和c在同一个监狱。如果继续枚举发现b和c会发生冲突，而之前为了避免更大的冲突发生，b和c已经放进了同一个监狱，所以这次冲突无法避免，该冲突就是要求的答案

4、按冲突从大到小枚举，用b[]数组保存最大的敌人（第一次枚举到的敌人），若最大的敌人为k1，则b[i]=k1，继续枚举发现i下次遇到其他敌人k2，将k1和k2放进同一个集合。（敌人的敌人就是朋友，将所有朋友放进同一个监狱）

5、枚举到某个冲突x,y时，发现之前已经把x,y放进了同一个监狱，说明为了避免之前的较大的冲突，导致该较小冲突无法避免，这个冲突就是答案

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n, m;
int fa[20005];//只有两个监狱，两个罪犯要么在同一个监狱，要么不在同一个监狱。
int b[20005];//存储i最大的敌人。
//若最大的敌人为k，则b[i]=k，下次遇到其他敌人t，只能将t和k在同一个监狱避免与i发生冲突
//这样尽可能满足冲突大的罪犯在不同的监狱里面，直到出现两个罪犯之前为了避免冲突已经放进了同一个监狱
struct node 
{
    int u, v;
    ll w;
}a[100005];
bool cmp(node a,node b) 
{
    return (a.w > b.w);
}

int find(int x)//查找x的集合编号
{  
    return(fa[x]==x?x:fa[x]=find(fa[x]));
}
void merge(int x, int y)//合并两个集合
{ 
    fa[find(x)] = find(y);
}

int main() 
{
    cin >> n >> m;
    for (int i = 1;i <= m;i++) cin >> a[i].u >> a[i].v >> a[i].w;
    for (int i = 1;i <= n;i++) fa[i] = i;//初始化，每个罪犯自己就是一个集合
    sort(a + 1, a + 1 + m, cmp);// 按照影响力从大到小排序，只需要找出最大的不可避免的冲突
    for (int i = 1;i <= m;i++)//从大到小遍历，尽量避免冲突，直到出现一个无法避免的冲突
    {
        if(find(a[i].u)==find(a[i].v))//冲突不可避免,之前已将这两个罪犯放到同一个集合内了
        {
            cout<<a[i].w<<endl;//由于是从大到小排序，这就是最大冲突了
            return 0;          
        }
        if(b[a[i].u]==0) b[a[i].u]=a[i].v;//u先前不存在敌人，用b[u]=v表示u最大的敌人是v
        else merge(a[i].v, b[a[i].u]);//u先前存在敌人b[i]，只能将v和b[i]放进同一个监狱
        if(b[a[i].v]==0) b[a[i].v] = a[i].u;//v先前不存在敌人，用b[v]=u表示v最大的敌人是u
        else merge(a[i].u, b[a[i].v]);//v先前存在敌人b[i]，只能将u和b[i]放进同一个监狱
    }
}