题解：关押罪犯问题

一、题目背景

S城有两座监狱，关押着N名罪犯，罪犯之间存在仇恨关系，用“怨气值”表示仇恨程度。若两名有仇恨的罪犯被关押在同一监狱，会发生影响力等于怨气值的冲突事件。警察局需将罪犯分配到两座监狱，使市长看到的冲突事件影响力最小，求这个最小值。

二、解题思路

本题采用二分答案和染色法判定二分图的方法求解。先对怨气值进行二分，假设当前二分的最大怨气值为 mid，将怨气值大于 mid 的边所连接的罪犯看作一个图，通过染色法判断该图是否为二分图。若是二分图，则说明可以将这些罪犯合理分配到两座监狱，避免产生大于 mid 的冲突事件；若不是二分图，则说明无法避免，需要增大 mid。最终找到满足条件的最小 mid 即为答案。

具体步骤如下：
1. 定义图的存储结构，包括邻接表相关数组、用于记录节点染色情况的数组 color[N]。
2. 编写添加边的函数 add，用于构建邻接表。
3. 实现深度优先搜索（DFS）函数 dfs，用于染色法判断二分图：
- 对当前节点进行染色，颜色为 c。
- 遍历当前节点的邻接边，若边的权值（怨气值）小于等于 mid，则跳过该边（因为这些边对应的冲突事件影响力在可接受范围内，无需考虑）。
- 若邻接节点已染色，检查其颜色是否与当前节点相同，若相同则说明不是二分图，返回 false。
- 若邻接节点未染色，对其进行染色（颜色为 3 - c），并递归调用 dfs，若递归结果为 false，则返回 false。
- 若所有邻接节点都处理完毕且未返回 false，则返回 true。
4. 实现检查函数 check，用于检查给定的 mid 是否满足条件：
- 初始化染色数组 color 为 0。
- 遍历所有节点，对未染色的节点调用 dfs 进行染色和判断。
- 若所有节点都能合理染色（即图为二分图），则返回 true，否则返回 false。
5. 在 main 函数中：
- 读取罪犯数量 n 和仇恨罪犯对数 m，初始化邻接表。
- 读取每对仇恨罪犯及其怨气值，构建图的邻接表。
- 对怨气值进行二分，初始左边界 l = 0，右边界 r = 1e9。
- 在二分过程中，调用 check 函数检查当前 mid 是否满足条件，若满足则缩小右边界，否则增大左边界。
- 二分结束后，输出最终结果 r，即市长看到的冲突事件影响力的最小值。

三、代码逐段分析

（一）头文件和全局变量

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20010, M = 200010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int color[N];

1. 头文件：
   • #include <cstdio>：用于标准输入输出函数，如 scanf 和 printf。
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供C++风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数。
   • using namespace std;：使用标准命名空间，以便直接使用标准库中的函数和类型。
2. 常量定义：
   • const int N = 20010, M = 200010;：定义节点的最大数量（罪犯数量）和边的最大数量。
3. 变量定义：
   • int n, m;：分别表示罪犯的数量和存在仇恨的罪犯对数。
   • int h[N], e[M], w[M], ne[M], idx;：邻接表相关数组，h[N] 存储每个节点的头指针，e[M] 存储边的终点，w[M] 存储边权（怨气值），ne[M] 存储下一条边的指针，idx 用于边的编号。
   • int color[N];：用于记录每个节点的染色情况，0 表示未染色，1 和 2 表示不同的颜色。

（二）添加边函数

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

该函数用于向邻接表中添加一条边，参数 a 为起点，b 为终点，c 为边权（怨气值）。通过更新邻接表数组，将边的信息存储起来。

（三）深度优先搜索（DFS）函数

bool dfs(int u, int c, int mid)
{
    color[u] = c;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (w[i] <= mid) continue;
        if (color[j])
        {
            if (color[j] == c) return false;
        }
        else if (!dfs(j, 3 - c, mid)) return false;
    }

    return true;
}

1. 对当前节点 u 进行染色，颜色为 c。
2. 遍历当前节点 u 的邻接边：
   • 若边的权值 w[i] 小于等于 mid，则跳过该边（因为这些边对应的冲突事件影响力在可接受范围内，无需考虑）。
   • 若邻接节点 j 已染色（color[j] 不为 0），检查其颜色是否与当前节点相同，若相同则说明不是二分图，返回 false。
   • 若邻接节点 j 未染色，对其进行染色（颜色为 3 - c），并递归调用 dfs，若递归结果为 false，则返回 false。
3. 若所有邻接节点都处理完毕且未返回 false，则返回 true。

（四）检查函数

bool check(int mid)
{
    memset(color, 0, sizeof color);
    for (int i = 1; i <= n; i ++ )
        if (!color[i])
            if (!dfs(i, 1, mid))
                return false;
    return true;
}

1. 初始化染色数组 color 为 0，表示所有节点未染色。
2. 遍历所有节点：
   • 若节点 i 未染色（!color[i]），对其调用 dfs 函数进行染色和判断，起始颜色为 1。
   • 若 dfs 函数返回 false，则说明以该节点为起点的子图不是二分图，返回 false。
3. 若所有节点都能合理染色（即图为二分图），则返回 true。

（五）main 函数

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    int l = 0, r = 1e9;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", r);

    return 0;
}

1. 读取罪犯数量 n 和仇恨罪犯对数 m，初始化邻接表（h 数组设为 -1）。
2. 读取每对仇恨罪犯及其怨气值，构建图的邻接表。
3. 对怨气值进行二分，初始左边界 l = 0，右边界 r = 1e9。
4. 在二分过程中：
   • 计算中间值 mid = l + r >> 1。
   • 调用 check 函数检查当前 mid 是否满足条件，若满足则缩小右边界 r = mid，否则增大左边界 l = mid + 1。
5. 二分结束后，输出最终结果 r，即市长看到的冲突事件影响力的最小值。
6. 程序结束。

四、时间复杂度和空间复杂度分析

（一）时间复杂度

1. 建图：读取 m 条边构建邻接表，时间复杂度为 (O(m))。
2. 二分查找：二分的次数为 (O(\log_{2}10^{9}))，每次二分调用 check 函数。
3. check 函数：遍历所有节点调用 dfs 函数，dfs 函数在最坏情况下会遍历所有边，时间复杂度为 (O(n + m))。所以每次 check 函数的时间复杂度为 (O(n + m))。
   总体时间复杂度为 (O(m + \log_{2}10^{9} \times (n + m)))。

（二）空间复杂度

1. 邻接表：存储边的信息，空间复杂度为 (O(m))。
2. 其他数组：染色数组 color[N] 等，空间复杂度为 (O(n))。
   总体空间复杂度为 (O(n + m))。

希望这份题解能帮助你理解这道题的解题思路和代码实现。如果有任何疑问，欢迎随时提问。