云剪贴板 & idea和小知识积累

正则二分图为所有点度数相等的二分图。

如果正则二分图有边，那么由 Hall 定理可以证明这个二分图必然有完美匹配。

判断一个数是否为两个平方数 (a^2) 和 (b^2) 的和 :

等价于奇质因子都是mod 4=1的数.

判断一个数是否为两个平方数 (a^2) 和 (b^2(gcd(a,b) = 1)) 的和 :

等价于奇质因子都是mod 4=1的数，并且不能是 4 的倍数。

那么就可以用分解质因数的方法check， (Theta(n^{frac{1}{4}} log n)) 或 (Theta(sqrt n))

二分图相关结论：

1、求二分图最大独立集：先求个最大匹配，然后从未匹配的左部点开始沿着残量网络 dfs , dfs到的左部点和未dfs到的右部点为最大独立集

2、求二分图最小覆盖：最大独立集的补集

3、求DAG最长反链：最长反链长度 = 最小可重链覆盖大小。

最长反链如何求方案：

先求出传递闭包，建出拆点二分图并求出其最大匹配(.)

考虑求出拆点二分图的最大独立集，左右都在最大独立集里的点(i)就在最长反链里(.)

4、匹配的必须边和可行边。

如果一个匹配边的两个端点在残量网络上强联通则这个不是必须边，反之亦然；

如果一个匹配边的两个端点在残量网络上强联通则这个是可行边，反之亦然；

5、一个点是否一定在一个完美匹配中：

考虑它的补集，即不在匹配上的点：从未匹配点上开始沿残量网络 dfs ， dfs 到的点就是不在匹配上的点。

竞赛图的一些性质：