结合二分

AcWing 257. 关押罪犯
确定二分图两个块内的最大边权的最小值

最大匹配建图

AcWing 372. 棋盘覆盖
NxM的矩阵如何建立二分图？
行列坐标和如果是奇数为一组，如果为偶数为另一组。

最小点覆盖

最小点覆盖：从图中选出最少的点，使得每一条边至少有一个端点被选择。

在二分图中：
最大匹配数 = 最小点覆盖 = 总点数- 最大独立集 = 总点数 - 最小路径点覆盖
证明：最大匹配数 = 最小点覆盖

  • 最小点覆盖 >= 最大匹配数，显然成立，因为最大匹配数每条边都互不相交，故每条边都得选出一个点。
  • 证明=可以成立
    • 先求出图的最大匹配，然后从左部的每个非匹配点出发，找一次增广路径，标记所有经过的点(可以得出，最后一个点一定是匹配点，因为如果最后一个点是非匹配点，可以将其变为匹配点并且对其它已匹配的边没有影响)，左部所有未被标记的点，右部所有被标记的点记为最小点覆盖(可以看出他们都是匹配点)
    • 左部所有非匹配点都被标记，右部所有非匹配点一定未被标记(增广路径的性质决定)
    • 对于每一个匹配边而言，左右两个点要么同时被标记，要么同时不被标记
    • 然后可以得出：对于左边的匹配点而言，要么被标记从而被其匹配点覆盖，要么未被标记，被选中作为覆盖点；对于左边的非匹配点来讲，一定是被标记的点，所以一定会被右边被标记的匹配点覆盖；对于右边的匹配点而言，如果被标记，他就是覆盖点，如果未被标记，则一定可以被左边的未标记匹配点覆盖；对于右边的非匹配点而言，其要么没有出边，要么其边对应的另一端为未标记的匹配点(如果不是的话这条边应该是匹配边产生矛盾)，而左边未标记的匹配点都被选作覆盖点，因此这些边也会被覆盖。得证

AcWing 376. 机器任务
最小覆盖点例题

最大独立集

最大独立集：从图中选出最多的点使得选出的点之间没有边。
最大团：从图中选出最多的点使得选出的点集中任意两点之间有边。

二分图中，最大独立集等价于去掉最少的点，将所有边都破坏掉
最大独立集 = 总点数- 最小点覆盖 = 总点数- 最大匹配数

AcWing 378. 骑士放置
最大独立集例题

最小路径点覆盖

也被称为最小路径覆盖，针对一个有向无环图，用最少的互不相交的路径覆盖所有点。

如何找最少的路径？
孤立点自己算一条路径
拆点，每个点拆成两个点，出点和入点，这样图就变成了一个完全二分图，原图中的每条边对应一个出点到入点之间的连线。
原图中的每条路径对应某些匹配，路径终点对应出点集中的一个非匹配点，目标是使路径终点数最少，即让出点集中的非匹配点最少，匹配点最多，即找到二分图的最大匹配。

二分图中：
总点数 - 最大匹配数 = 最小路径点覆盖

最小路径可重复点覆盖

可重复是指不同路径上可能有重复点

  1. 求原图的传递闭包
  2. 在新图上求最小路径点覆盖

AcWing 379. 捉迷藏
最小路径可重复点覆盖