题解：捉迷藏问题

一、题目背景

Vani和cl2在由 (N) 座房子和 (M) 条有向道路组成的有向无环图树林里捉迷藏。沿着道路能相互望见，cl2要选 (K) 座房子作为藏身点，且这些藏身点两两之间无路径相连，cl2想知道最多能选出多少个藏身点。

二、解题思路

本题可通过传递闭包和二分图最大匹配来求解。先利用Floyd算法的思想求出图的传递闭包，得到任意两点之间是否存在路径。然后将问题转化为求二分图的最大独立集，把图中的点分成两部分（这里不区分具体分组方式，因为最终目的是求独立集），求最大匹配，用总点数减去最大匹配数就是最大独立集的大小，即最多能选出的藏身点数量。

具体步骤如下：
1. 定义相关数组和变量，包括存储图的传递闭包的二维数组 d[N][N]（true 表示两点之间存在路径）、标记节点是否已访问的数组 st[N]、记录匹配情况的数组 match[N]。
2. 编写匈牙利算法的核心函数 find，用于寻找增广路径：
- 遍历与当前节点 x 存在路径的所有节点 i。
- 检查节点 i 是否未被访问。
- 标记节点 i 为已访问，若节点 i 未匹配，或者能通过递归找到增广路径，则更新匹配关系并返回 true。
- 若所有相连节点都无法找到增广路径，则返回 false。
3. 在 main 函数中：
- 读取房子数量 n 和道路数量 m。
- 读取每条道路的起点和终点，更新图的邻接关系数组 d。
- 利用Floyd算法的思想求传递闭包，即对于任意三个节点 i、j、k，若 i 到 k 有路径且 k 到 j 有路径，则 i 到 j 有路径（d[i][j] |= d[i][k] & d[k][j]）。
- 初始化结果变量 res 为 (0)，遍历所有节点，调用 find 函数进行匹配尝试，若匹配成功则结果 res 加 (1)。
- 输出最多能选出的藏身点数量，计算公式为 n - res（n 是总点数，res 是最大匹配数）。

三、代码逐段分析

（一）头文件和全局变量

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

using namespace std;

const int N = 210, M = 30010;

int n, m;
bool d[N][N], st[N];
int match[N];

1. 头文件：
   • #include <cstdio>：用于标准输入输出函数，如 scanf 和 printf。
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供C++风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数。
2. 常量定义：const int N = 210, M = 30010; 分别定义节点的最大数量（房子数量）和边的最大数量（道路数量）。
3. 变量定义：
   • int n, m;：分别表示房子的数量和道路的数量。
   • bool d[N][N], st[N];：d[N][N] 表示图的传递闭包，true 表示两个节点之间存在路径；st[N] 用于标记在一次匹配尝试中，节点是否已被访问。
   • int match[N];：数组，存储每个节点的匹配对象，0 表示未匹配。

（二）匈牙利算法函数 find

bool find(int x)
{
    for (int i = 1; i <= n; i ++ )
        if (d[x][i] && !st[i])
        {
            st[i] = true;
            int t = match[i];
            if (t == 0 || find(t))
            {
                match[i] = x;
                return true;
            }
        }

    return false;
}

1. 遍历所有节点 i：
   • 检查节点 i 与当前节点 x 之间是否存在路径（d[x][i]）且节点 i 未被访问（!st[i]）。
2. 若节点 i 满足条件：
   • 标记节点 i 为已访问（st[i] = true;）。
   • 获取节点 i 当前的匹配情况 t。
   • 若节点 i 未匹配（t == 0），或者能通过递归调用 find 函数为节点 i 的当前匹配对象找到新的匹配（find(t)），则更新节点 i 的匹配为节点 x，并返回 true。
3. 若所有节点都无法找到增广路径，则返回 false。

（三）main 函数

int main()
{
    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        d[a][b] = true;
    }

    // 传递闭包
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] |= d[i][k] & d[k][j];

    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        memset(st, 0, sizeof st);
        if (find(i)) res ++ ;
    }

    printf("%d\n", n - res);

    return 0;
}

1. 读取房子数量 n 和道路数量 m。
2. 读取每条道路的起点 a 和终点 b，在数组 d 中标记从 a 到 b 存在路径（d[a][b] = true;）。
3. 求图的传递闭包：
   • 利用三层循环，对于任意三个节点 i、j、k，若 i 到 k 有路径且 k 到 j 有路径，则更新 i 到 j 有路径（d[i][j] |= d[i][k] & d[k][j]）。
4. 初始化结果变量 res = 0，遍历所有节点 i：
   • 每次匹配尝试前，将访问标记数组 st 清零。
   • 调用 find 函数进行匹配尝试，若匹配成功（find(i) 返回 true），则结果 res 加 (1)。
5. 输出最多能选出的藏身点数量，计算公式为 n - res。
6. 程序结束。

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

（一）时间复杂度

1. 读入数据：读取道路信息，时间复杂度为 (O(m))，其中 (m) 是道路数量。
2. 传递闭包：使用三层循环求传递闭包，时间复杂度为 (O(n^3))，其中 (n) 是房子数量。
3. 匈牙利算法：对于每个节点，最多进行 (O(n)) 次匹配尝试，而总共有 (n) 个节点，所以匈牙利算法的时间复杂度为 (O(n^2))。
   总体时间复杂度为 (O(m + n^3 + n^2))，在本题数据范围内 (O(n^3)) 起主导作用。

（二）空间复杂度

1. 数组空间：传递闭包数组 d[N][N] 空间复杂度为 (O(n^2))，匹配数组 match[N] 空间复杂度为 (O(n))，访问标记数组 st[N] 空间复杂度为 (O(n))。
   总体空间复杂度为 (O(n^2))。

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