洛谷之关押罪犯

洛谷-P1525 关押罪犯

https://www.luogu.com.cn/problem/P1525

首先分析题目，题目的意思就是让我们将罪犯分到两个监狱，使两个监狱中的最大仇恨尽可能最小，那么我们肯定要先对仇恨进行从大到小的排序,然后尽可能别把仇恨大的给拆散。这里需要用到并查集，俗话说的好：敌人的敌人就是朋友，因此除了并查集外，我们还要设置个储存敌人的数组。

代码如下

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<stack>
#include<algorithm>
#include<vector>
#include<map>
#define MAXN 0x3f3f3f3f
using namespace std;
int n, m;
int fa[100000], fb[100000];//fa表示并查集，fb表示罪犯之间的仇恨对象
struct MS{
    int u;
    int v;
    int w;
}T[100000];
bool cmp(MS x,MS y)//sort重载
{
    if(x.w!=y.w)
        return x.w > y.w;
}
int findx(int x)//查找
{
    if(x!=fa[x])
        fa[x] = findx(fa[x]);
    return fa[x];
}
void make_set()//初始化并查集
{
    for (int i = 1; i <= n;i++)
    {
        fa[i] = i;
    }
}
void unity(int x,int y)//合并
{
    int x1 = findx(x);
    int y1 = findx(y);
    if(x1!=y1)
    {
        fa[x1] = y1;
    }
}
int main()
{
    memset(fb ,0,sizeof(fb));
    cin >> n >> m;
     make_set();
    for (int i = 1; i <= m;i++)
    {
        cin >> T[i].u >> T[i].v >> T[i].w;
    }
    sort(T + 1,T+ m + 1,cmp);
    for (int i = 1; i <= m;i++)
    {
        if(findx(T[i].u)==findx(T[i].v))//如果有矛盾的分在了一个监狱，直接输出怒气值
        {
            cout << T[i].w;
            return 0;
        }
        if(!fb[T[i].u])//如果没有敌人
        {
           fb[T[i].u] = T[i].v;//u的敌人为v
        }
        else{
            unity(fb[T[i].u], T[i].v);//敌人的敌人就是朋友
        }
       if(!fb[T[i].v])//如果没有敌人
        {
            fb[T[i].v] = T[i].u;//v的敌人为u
        }
        else{
            unity(fb[T[i].v],T[i].u);//敌人的敌人就是朋友
        }
      
    }
    cout << '0';
    return 0;
}