[算法] 二分图最小点覆盖构造方案+Konig定理证明

博主很笨 ，如有纰漏，欢迎在评论区指出讨论。

二分图的最大匹配使用 \(Dinic\) 算法进行实现，时间复杂度为 \(O(n\sqrt{e})\)，其中， \(n\)为二分图中左部点的数量， \(e\) 为二分图中的边数。若是匈牙利算法，时间复杂度为 \(O(nm)\) ， \(m\) 为二分图中右部点的数量，不建议使用。

文章中的例题链接。

定理内容：二分图最小点覆盖的点的数量等于二分图最大匹配的边的数量。

构造方法 \(+\) 简单证明：

首先求出二分图中的最大匹配，建议使用 \(Dinic\) 。

从每一个非匹配点出发，沿着非匹配边正向进行遍历，沿着匹配边反向进行遍历到的点进行标记。选取左部点中没有被标记过的点，右部点中被标记过的点，则这些点可以形成该二分图的最小点覆盖。

遍历代码实现如下：

那么就有以下性质：

有了上述的三条性质，可以发现：按照选取左部点中没有被标记过的点，右部点中被标记过的点的规则，选出来的点的点数必然为最大匹配的边数。左部的非匹配点必然被访问，则必不会被选，右部的非匹配点必不会被访问，则必不会被选。而第三条性质决定了，对于一组匹配点，会选择有且仅有一个点。故而选出的点的点数等于最大匹配的边数。

其次需要解决一个问题：保证这些点覆盖了所有的边。具体可以分为四类：

最后在确保这是最小的方案：反证法，少选一个点，那么至少有一条匹配边会被不选，不满足点覆盖的定义，矛盾。也就是说，至少每一条匹配边都需要选一个点。

如上，证毕。

题目来源：COCI 2019/2020 Contest #6 T4. Skandi

给定一个 \(n\times m\) 的矩阵，其中的白色点为 \(0\) ， 黑色点为 \(1\) 。黑色点可以往下一直扩展到底部，把白色点变成蓝色点，直到遇到黑色点为止。同理，也可向右扩展。问整个矩阵经过最小多少次扩展才能扩展为整个矩阵到不存在白色，并打印出每次扩展是从哪个点开始的，并打印出扩展方向。题目满足第一行第一列一定为黑色点。

一道建模题。

一个白色点变为蓝色点只有两种方法，从它上方或左方的黑色点扩展而来，且只需要一个点扩展即可。可以考虑到最小点覆盖问题。

由于对于一个黑色点来说，它可以往右或往下扩展。那么它就有两个身份，也就是说一个点拥有两个编号。一个编号为把整个矩阵拉成一条链的顺序，另一个编号为前一个编号 \(+n\times m\) ，这样不会发生冲突。获得编号的函数：

那么不难发现一个白色点，与其相关的是一个编号 \(\leqslant n\times m\) 的点，和一个编号 \(>n\times m\) 的点。把这两个点连接起来，就是一张二分图。

问题就转换为找这张图的最小点覆盖问题。使用 \(Dinic\) ，在根据上述 \(König\) 定理构造即可。

边数为白点的个数，左部点为黑点的个数，则时间复杂度为 \(O(nm\sqrt{nm})\) ，即 \(O(n^{\frac{3}{2}}m^{\frac{3}{2}})\) ，本题的 \(n\) ， \(m\) 均小于 \(500\) ，大概能够在 \(1s\) 内求出答案。