/**************************************************************** 
 * Description: NOIP2010  T3  关押罪犯  二分图
 * Author: Alex Li
 * Date: 2024-08-13 10:07:16
 * LastEditTime: 2024-08-13 10:14:42
****************************************************************/
bool work(int mid) {
    queue<int> q;  // 用于广度优先搜索（BFS）的队列
    int color[20009] = {0};  // 用于存储每个节点的颜色，初始为0表示未染色

    // 对每个节点进行遍历，判断图是否可以用两种颜色染色（即判断是否是二分图）
    for (int i = 1; i <= n; i++) {
        if (!color[i]) {  // 如果节点 `i` 未被染色
            q.push(i);  // 将节点 `i` 加入队列
            color[i] = 1;  // 给节点 `i` 染上颜色1

            // 进行广度优先搜索（BFS）
            while (!q.empty()) {
                int x = q.front();  // 取出队列的前端元素
                q.pop();  // 将前端元素出队

                // 遍历所有与节点 `x` 相邻的边
                for (int i = head[x]; i; i = p[i].from) {
                    // 只考虑权重大于等于 `mid` 的边
                    if (p[i].w >= mid) {
                        // 如果相邻节点 `p[i].to` 未被染色
                        if (!color[p[i].to]) {
                            q.push(p[i].to);  // 将相邻节点加入队列

                            // 给相邻节点染上与 `x` 节点相反的颜色
                            color[p[i].to] = (color[x] == 1) ? 2 : 1;
                        } 
                        // 如果相邻节点已经染色，并且颜色与 `x` 节点相同，说明无法二分
                        else if (color[p[i].to] == color[x]) {
                            return false;  // 返回 false，表示无法用 `mid` 的仇恨值形成二分图
                        }
                    }
                }
            }
        }
    }
    // 如果所有节点成功染色且未出现矛盾，返回 true，表示可以用 `mid` 作为仇恨值形成二分图
    return true;
}


/*针对“关押罪犯”这个问题，代码使用了**二分查找**和**染色法**（判断二分图）来找到最小的可能导致冲突的最大怨气值。以下是代码的逻辑解释：

### 题目背景
题目要求将罪犯分配到两座监狱中，目的是尽量减少同一监狱中两名罪犯之间的最大冲突影响力。为此，我们需要找到使得在同一监狱中的任意两名罪犯的最大怨气值尽可能小的分配方案。

### 代码的主要思路
1. **二分查找最大怨气值**：
   - 我们将所有的仇恨值（怨气值）进行二分查找。设定一个中间值 `mid`，判断能否用 `mid` 作为阈值，将罪犯分成两个集合（监狱），使得同一集合内任意两罪犯之间的仇恨值都小于 `mid`。

2. **染色法判断二分图**：
   - 对于一个特定的 `mid`，我们用染色法判断能否将图染成二分图。具体来说，我们尝试将每个节点（罪犯）染上两种颜色之一（表示两个不同的监狱），使得相邻的两个节点（有仇恨的两个罪犯）颜色不同。
   - 如果能成功完成染色，说明以当前的 `mid` 值可以将图划分为二分图，即可以将罪犯分为两部分，使得同一部分内没有超过 `mid` 的仇恨值。
   - 如果不能染色成功，则表示以当前 `mid` 值无法完成分配，需要尝试更大的 `mid` 值。

3. **最终结果**：
   - 最后得到的 `L` 值，即为我们可以实现的最小的“市长看到的最大冲突事件的影响力”。

### 代码逻辑详细解释
1. **输入部分**：
   - 首先读取罪犯数 `n` 和仇恨对数 `m`。
   - 然后读取每一对罪犯之间的仇恨值，并构建无向图（用边表示罪犯间的仇恨关系）。

2. **初始化二分查找的边界**：
   - `R` 是仇恨值中的最大值（加1后用于二分查找的右边界）。
   - `L` 是二分查找的左边界，初始为0。

3. **二分查找主循环**：
   - 不断缩小 `L` 和 `R` 之间的范围，直到 `R` 和 `L` 相差不超过1。
   - 在每次迭代中，计算 `mid`，然后使用 `work(mid)` 来判断是否可以以 `mid` 作为阈值将图分为二分图。

4. **判断是否为二分图**：
   - `work(mid)` 函数通过广度优先搜索（BFS）来尝试给图中的节点染色，判断是否可以用 `mid` 阈值成功染色。
   - 如果染色成功，说明当前 `mid` 可以作为阈值；否则，说明需要更大的 `mid`。

5. **输出结果**：
   - 当二分查找完成后，`L` 是我们需要的最小的最大仇恨值，即市长看到的最大冲突事件的影响力。

### 代码效果
- 该算法通过二分查找的方式有效地减少了搜索范围，并且利用染色法判断是否可以将罪犯分配到两个监狱中，避免了暴力搜索的高计算成本。
- 最终结果是使得市长看到的最大冲突影响力最小化，从而找到最佳的罪犯分配方案。*/