379 捉迷藏（最小路径重复点覆盖）

1. 问题描述：

Vani 和 cl2 在一片树林里捉迷藏。这片树林里有 N 座房子，M 条有向道路，组成了一张有向无环图。树林里的树非常茂密，足以遮挡视线，但是沿着道路望去，却是视野开阔。如果从房子 A 沿着路走下去能够到达 B，那么在 A 和 B 里的人是能够相互望见的。现在 cl2 要在这 N 座房子里选择 K 座作为藏身点，同时 Vani 也专挑 cl2 作为藏身点的房子进去寻找，为了避免被 Vani 看见，cl2 要求这 K 个藏身点的任意两个之间都没有路径相连。为了让 Vani 更难找到自己，cl2 想知道最多能选出多少个藏身点。

输入格式

输入数据的第一行是两个整数 N 和 M。接下来 M 行，每行两个整数 x，y，表示一条从 x 到 y 的有向道路。

输出格式

输出一个整数，表示最多能选取的藏身点个数。

数据范围

N ≤ 200，M ≤ 30000

输入样例：

7 5
1 2
3 2
2 4
4 5
4 6

输出样例：

3
来源：https://www.acwing.com/problem/content/description/381/

2. 思路分析：

分析题目可以知道已知一个有向图（DAG），让我们从中选择最多的点使得任意两点不能够从一个点走到另外一个点，也即任意两点不可达，并且路径之间允许有交集的，也即可以存在公共点，属于最小路径重复点覆盖问题，最小路径重复点覆盖问题属于最小路径点覆盖问题的一个扩展，最小路径点覆盖又称为最小路径覆盖，是针对于有向无环图来说的，我们希望使用最少的互不相交的路径将所有的点覆盖住（路径中的点是不能够重复的），最小路径点覆盖需要到拆点，这个拆点的方式比较独特：

原图中存在i-->j的路径则i向j'连一条边，连的边是有向的，但是在具体实现的时候看成是无向边，得到的新图一定是二分图，下面是一个有向无环图的例子：

在二分图中最小路径点覆盖 = 总点数 - 最大匹配数（res  = n - m），这里的总点数是指左部和右部的总点数之和，每一个点最多有一个出度和入度，每一个点至多在一条路径中，所以一定是一个匹配，其中存在两个关键点：

• 新图中的路径等价于匹配
• 路径终点等价于左部的非匹配点

原图中求解最少互不相交的路径等价于求解新图中左部的最少的非匹配点的数量，等价于让左侧的非匹配点数量最少，等价于让左侧的匹配点最多，等价于在新图中找最大匹配，新图中左部的总点数减去最大匹配的数量就是最小路径点覆盖。而对于最小路径重复点覆盖，则是最小路径点覆盖的一个扩展，允许路径覆盖点的路径有公共点，最小路径重复点覆盖的的求解主要有两个步骤：

• 求解传递闭包G'（原图为G），传递闭包：如果i-->k有路径，k->j有路径那么i向j一条边
• 在新图G'求解最小路径覆盖

也即原图中的最小路径重复点覆盖等价于在新图中求解最小路径点覆盖，其实可以发现这两者是一一对应的关系，对于原图中任意一种覆盖方式都可以转化为新图中不重复的覆盖方式，并且需要的路径数量是相等的，同理右边的覆盖方式也可以对应坐标的覆盖方式，所以原图的路径重复点覆盖等于新图的路径覆盖，最终的答案为最小路径重复点覆盖的数量 = n - 新图中的最大匹配，这个结论的证明还是比较复杂的。如最小路径重复点覆盖有cnt条，那么说明cnt条路线可以将所有的点覆盖住，而我们需要在这里cnt路线上选，并且每一条路径最多只能够选择一个点，也即答案小于等于cnt，接下来就是构造一种方案使得选出的点的数量的等于cnt，说明答案就是cnt。构造的比较独特，这里就没有写如何构造了，知道有一种构造的方式使得最小路径重复点覆盖的数量等于cnt就可以了。

3. 代码如下：

from typing import Listclass Solution:# 在新图上求解最小路径覆盖因为求解最小路径覆盖是需要拆点的, 但是在实际的过程中我们并没有拆点, 其实在做完floyd算法之后其实是可以看成拆成了两个点, floyd算法求解完传递闭包之后那么每一个间接到达的边都有一条直接连在一起的边def find(self, u: int, n: int, st: List[int], match: List[int], d: List[List[int]]):for i in range(1, n + 1):if st[i] == 0 and d[u][i] == 1:st[i] = 1if match[i] == -1 or self.find(match[i], n, st, match, d):match[i] = ureturn Truereturn Falsedef process(self):n, m = map(int, input().split())        #  因为后面在floyd算法的时候只需要判断两点之间是否有边即可, 不涉及到权重所以在原数组中进行操作也是没有影响的g = [[0] * (n + 10) for i in range(n + 10)]for i in range(m):x, y = map(int, input().split())# 有向图g[x][y] = 1# 题目中的测试数据都是以1开始编号的for k in range(1, n + 1):for i in range(1, n + 1):for j in range(1, n + 1):# k是i->j的中间点那么i->j连一条边g[i][j] |= 1 if g[i][k] and g[k][j] else 0match = [-1] * (n + 10)res = 0for i in range(1, n + 1):st = [0] * (n + 10)if self.find(i, n, st, match, g):res += 1# 二分图中总点数 - 最大匹配 = 最小路径点覆盖return n - resif __name__ == "__main__":print(Solution().process())