Luogu P1525 关押罪犯

题目描述

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

并查集简单题

Solution

很显然这道题可以贪心处理

我们将敌对关系按照权值从大到小排序

由于只有两个监狱，一种比较简单的处理方式是对于一对罪犯，如果一人已在一个监狱中，则将另一人放到另一监狱

如果两人在同一监狱则直接得到答案

如果两人都不在监狱中，则将两人分别放到两个监狱中

这样处理的唯一问题就是两人都不在监狱中时无法进行分配，随便放可能会影响到后续罪犯的放置

所以我们干脆摒弃监狱，直接使用并查集记录在同一监狱中的人，然后对于每个人记录不能在同一监狱中的第一个人

因为和同一人敌对的人一定在同一监狱，所以实际上只使用一个并查集即可

#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 20010
#define maxm 100010
#define cn const node 
using namespace std;

int n, m;

struct node {
    int u, v, w;

    friend bool operator < (cn &u, cn &v) { return u.w > v.w; } 
} a[maxm];

int fa[maxn], e[maxn]; 
void init_fa() { for (int i = 1; i <= n; ++i) fa[i] = i; }

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

inline void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return ; 
    fa[fx] = fy;
}

int ans; 
int main() {
    cin >> n >> m; 
    for (int i = 1; i <= m; ++i) scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].w);
    sort(a + 1, a + m + 1); init_fa();
    for (int i = 1; i <= m; ++i) {
        int u = a[i].u, v = a[i].v, w = a[i].w, fu = find(u), fv = find(v);
        if (fu == fv) { ans = w; break; }
        if (!e[u]) e[u] = v;
        else merge(e[u], v);
        if (!e[v]) e[v] = u;
        else merge(e[v], u); 
    }
    cout << ans << endl; 
    return 0;
}