题解：罪犯分配最小冲突问题（二分答案 + 扩展域并查集）

一、解题核心思路

本题的核心是 最小化最大冲突影响力，属于典型的「最小最大问题」，适合用 二分答案 结合 扩展域并查集 求解：

1. 二分答案：假设当前二分的阈值为 mid，我们需要判断是否存在一种分配方案，使得所有怨气值 大于 mid 的罪犯对都被分到不同监狱（即这些高怨气值的罪犯对不会发生冲突）。如果能满足，则说明 mid 是一个可行解，可尝试更小的阈值；否则需要增大阈值。
2. 扩展域并查集：用于判断「是否能将高怨气值的罪犯对分到不同监狱」。扩展域并查集通过给每个罪犯分配两个节点（自身域 x 和对立域 x + N），表示「x 所在监狱」和「x 不能所在的监狱」，从而用并查集维护「必须同狱」和「必须异狱」的约束关系。

二、关键原理

1. 二分答案逻辑：

   • 目标是找到最小的 ans，使得所有怨气值 > ans 的罪犯对都能被分到不同监狱（无冲突），而怨气值 ≤ ans 的罪犯对可以有冲突（不影响市长看到的最大冲突）。
   • 二分的范围：low = 0，high = 最大怨气值。

2. 扩展域并查集逻辑：

   • 每个罪犯 x 有两个节点：x（表示 x 在监狱 A）和 x + N（表示 x 在监狱 B，即与 x 对立）。
   • 对于怨气值 > mid 的罪犯对 (a, b)：必须将 a 和 b 分到不同监狱，因此：
     • 合并 a 和 b + N（a 在 A 则 b 必须在 B）；
     • 合并 a + N 和 b（a 在 B 则 b 必须在 A）。
   • 约束冲突判断：如果合并前 a 和 b 已在同一集合（必须同狱），或 a + N 和 b + N 已在同一集合（必须同狱），则无法满足「异狱」约束，当前 mid 不可行。

三、具体解题步骤

1. 输入读取与预处理：读取 N、M 和所有罪犯对，记录最大怨气值作为二分的 high。
2. 二分答案框架：初始化 low = 0，high = 最大怨气值，ans = 最大怨气值。
3. 可行性检查（核心）：对当前 mid，用扩展域并查集判断是否能满足所有怨气值 > mid 的罪犯对异狱：
   • 初始化并查集（大小为 2N，因为每个罪犯有两个域）。
   • 遍历所有怨气值 > mid 的罪犯对 (a, b)：
     • 若 a 和 b 已在同一集合，或 a + N 和 b + N 已在同一集合 → 冲突，mid 不可行。
     • 否则合并 a 与 b + N、a + N 与 b。
   • 若所有高怨气对都能满足异狱约束 → mid 可行，尝试更小的阈值；否则增大阈值。
4. 输出结果：二分结束后，ans 即为最小的最大冲突影响力。

四、完整代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 20005;
const int MAX_M = 100005;

// 扩展域并查集：parent[x] 表示 x 的父节点（x 范围 1~2N）
int parent[2 * MAX_N];

// 并查集查找（带路径压缩）
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// 初始化并查集
void init(int n) {
    for (int i = 1; i <= 2 * n; ++i) {
        parent[i] = i;
    }
}

// 可行性检查：判断 mid 是否为可行解
bool is_possible(int n, int m, const vector<tuple<int, int, int>>& crimes, int mid) {
    init(n);
    for (const auto& [a, b, c] : crimes) {
        if (c <= mid) continue; // 只处理怨气值 > mid 的罪犯对
        int root_a = find(a);
        int root_b = find(b);
        int root_a_opp = find(a + n); // a 的对立域
        int root_b_opp = find(b + n); // b 的对立域
        
        // 若 a 和 b 必须同狱，或 a对立和 b对立必须同狱 → 冲突
        if (root_a == root_b || root_a_opp == root_b_opp) {
            return false;
        }
        // 合并 a 和 b对立，a对立和 b
        parent[root_a] = root_b_opp;
        parent[root_a_opp] = root_b;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector<tuple<int, int, int>> crimes(M);
    int max_c = 0;
    for (int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        crimes[i] = {a, b, c};
        max_c = max(max_c, c);
    }

    int low = 0, high = max_c;
    int ans = max_c;
    // 二分答案
    while (low <= high) {
        int mid = (low + high) / 2;
        if (is_possible(N, M, crimes, mid)) {
            ans = mid;
            high = mid - 1; // 尝试更小的可行解
        } else {
            low = mid + 1; // 增大阈值
        }
    }

    cout << ans << endl;
    return 0;
}

五、代码解释

1. 扩展域并查集实现：
   • parent 数组大小为 2N，涵盖每个罪犯的「自身域」和「对立域」。
   • find 函数带路径压缩，提高查询效率；init 函数初始化每个节点的父节点为自身。
2. 可行性检查函数：
   • 遍历所有高怨气值（> mid）的罪犯对，通过合并对立域维护「必须异狱」约束。
   • 若发现约束冲突（无法异狱），直接返回 false，表示当前 mid 不可行。
3. 二分答案框架：
   • 不断缩小二分范围，找到最小的可行 mid，即为答案。

六、复杂度分析

• 时间复杂度：$O(M \log C)$，其中 $C$ 是最大怨气值（≤ $10^9$，$\log C$ ≈ 30）。每次可行性检查的时间为 $O(M \alpha(N))$（$\alpha$ 是并查集的阿克曼函数，近似常数），总时间为 $O(M \log C \alpha(N))$，完全适配 $N \leq 2e4$、$M \leq 1e5$ 的数据范围。
• 空间复杂度：$O(N)$，用于存储并查集的 parent 数组（大小 $2N$）。

该方法通过二分答案将「最小最大问题」转化为「可行性检查问题」，再用扩展域并查集高效解决可行性检查，是解决此类二分图判定+最小最大问题的经典方案。