博主很笨 ，如有纰漏，欢迎在评论区指出讨论。
二分图的最大匹配使用 \(Dinic\) 算法进行实现，时间复杂度为 \(O(n\sqrt{e})\)，其中， \(n\)为二分图中左部点的数量， \(e\) 为二分图中的边数。若是匈牙利算法，时间复杂度为 \(O(nm)\) ， \(m\) 为二分图中右部点的数量，不建议使用。
文章中的例题链接。
König定理定理内容：二分图最小点覆盖的点的数量等于二分图最大匹配的边的数量。
构造方法 \(+\) 简单证明：
首先求出二分图中的最大匹配，建议使用 \(Dinic\) 。
从每一个非匹配点出发，沿着非匹配边正向进行遍历，沿着匹配边反向进行遍历到的点进行标记。选取左部点中没有被标记过的点，右部点中被标记过的点，则这些点可以形成该二分图的最小点覆盖。
遍历代码实现如下：
void dfs(int now) { vis[now] = true; int SIZ = v[now].size(); for(int i = 0; i < SIZ; i++) { int next = v[now][i].to; if(vis[next] || !v[now][i].val)//正向边的容量为0说明是匹配边，反向边的容量为0说明是非匹配边 continue; dfs(next); } }那么就有以下性质：
若该点为左边的非匹配点，则这个点必被访问，因为这个点是整个 \(dfs\) 的起点
若该点为右边的非匹配点，则这个点必不会被访问，若是由左边的非匹配点才到达了这个点，那么可以将这条边变为匹配边，则匹配数 \(+1\) ，与最大匹配相冲突。若是左边的匹配点才到达了这个点，那么这个点的路径为左边非匹配点 → 右边匹配点 → 左边非匹配点 → 右边匹配点 → …… → 左边匹配点 → 右边非匹配点 ，很明显，上述路径为增广路，与最大匹配相冲突。所以，右边的非匹配点必不会被访问。
对于一组匹配点，要么两个都被标记，要么都不被标记。因为左部的匹配点是由右部的匹配点来遍历到的，出现必然成双成对。
有了上述的三条性质，可以发现：按照选取左部点中没有被标记过的点，右部点中被标记过的点的规则，选出来的点的点数必然为最大匹配的边数。左部的非匹配点必然被访问，则必不会被选，右部的非匹配点必不会被访问，则必不会被选。而第三条性质决定了，对于一组匹配点，会选择有且仅有一个点。故而选出的点的点数等于最大匹配的边数。
其次需要解决一个问题：保证这些点覆盖了所有的边。具体可以分为四类：
左部为非匹配点，右部为非匹配点。性质二已经讨论过，不可能出现这种情况，出现就不满足最大匹配的前提。
左部为匹配点，右部为非匹配点。同理性质二，路径类似，会出现增广路，那么这个左部的匹配点一定没有被访问过，必然被选。
左部为匹配点，右部为匹配点。一对匹配点中必选一个。
左部为非匹配点，右部为匹配点。这条边为非匹配边，而起点就是从左部的非匹配点点开始，那么右部的这个点必然被访问过，必然被选。
最后在确保这是最小的方案：一条边都只选了一个点，不存在浪费。
如上，证毕。
题目来源：COCI 2019/2020 Contest #6 T4. Skandi
题目大意给定一个 \(n\times m\) 的矩阵，其中的白色点为 \(0\) ， 黑色点为 \(1\) 。黑色点可以往下一直扩展到底部，把白色点变成蓝色点，直到遇到黑色点为止。同理，也可向右扩展。问整个矩阵经过最小多少次扩展才能扩展为整个矩阵到不存在白色，并打印出每次扩展是从哪个点开始的，并打印出扩展方向。题目满足第一行第一列一定为黑色点。
思路一道建模题。
一个白色点变为蓝色点只有两种方法，从它上方或左方的黑色点扩展而来，且只需要一个点扩展即可。可以考虑到最小点覆盖问题。
由于对于一个黑色点来说，它可以往右或往下扩展。那么它就有两个身份，也就是说一个点拥有两个编号。一个编号为把整个矩阵拉成一条链的顺序，另一个编号为前一个编号 \(+n\times m\) ，这样不会发生冲突。获得编号的函数：
int GetHash(int i, int j) { return (i - 1) * m + j; }那么不难发现一个白色点，与其相关的是一个编号 \(\leqslant n\times m\) 的点，和一个编号 \(>n\times m\) 的点。把这两个点连接起来，就是一张二分图。
问题就转换为找这张图的最小点覆盖问题。使用 \(Dinic\) ，在根据上述 \(König\) 定理构造即可。