Prutekoi's blog

8.1 白天讲的都是OI无关...
营员交流，干货许多，大家太强了

KM的扩展

xyx的工作，是把KM修改了一下使得它可以小常数 $O(n^3)$ 对所有匹配数求出最大权匹配，即功能完全包含费用流。

这里提一下费用流，SPFA+EK是 $O(n^4)$ 的，dijk+EK是 $O(n^3\log n)$ 的。特别地，在二分图最大权匹配问题中dijk可以去掉堆优化，得到 $O(n^3)$ 的算法。然而常数很大，是BM的几倍乃至十几倍。

回到BM，具体的做法是我们初始时把所有的左部点的顶标设为 $inf$（所有边权的max也可以，主要是为了都相等），然后之前我们每次增广是选一个左部点开始，现在改为从所有未匹配的左部点开始。（这些点就都在“交错树”的集合中，都被slack计入，其实就是交错森林了），然后就与之前的操作一样了（每次找到最小的slack，改变顶标，扩展交错森林，直到找到一条增广路）。

大概理解一下这个算法的正确性，我们归纳地想，假设当前交错森林中的左部点 $x$ 的顶标都满足等于 $b_x+C$，其中 $b_x$ 是根到这个点路径上偶数边权和减奇数边权和，$C$ 是一个常数。即它们的贡献相对大小都是准确的，只是都加了一个常数。那么考虑一次增广，考虑新加入的两条边，这时画画图就发现仍然满足条件，而森林中左部点都减去slack的操作就是调整了一下 $C$。而初始时设为相等的顶标就是为了满足初始的条件，就可以归纳了。
然后再注意一下一旦一个点成为了匹配点就会一直是匹配点。于是得到右部的非匹配点的顶标一定为 $0$（因为从来没有在交错森林内）。满足这样的条件之后，我们就发现找到最小的slack的操作就相当于找到最长的增广路。于是它就做到了费用流的事情。

$O(mo \log mo)$ 的多点求值

在 $n$ 比较大的时候由于多点求值常数大，所以可能跑不过 $O(n\log n)$ 的大常数多点求值。
zyy介绍了一个 $O(mo \log mo)$ 的多点求值。它是可以一次求出 $0\leq x<mo$ 的所有 $x$ 的值。所以它大概也可以通过强制在线把多点求值卡掉...
主要想法是先把 $mo$ 分解质因数。
对于模质数 $p$，它存在原根，我们直接用bluestein做一遍任意基dft就能得到所有的点值。
对于模 $p^k$，它也存在原根，类似做可以得到所有与 $p^k$ 互质的位置的点值。其他位置只有 $k$ 个，暴力做即可。
对于模 $2^k,k>2$，它不存在原根，但是经过复杂的证明可以得到 $\pm3^0,\pm3^1,...\pm3^{2^{c-2}}$ 模意义下互不相同且都与 $2$ 互质。那么仍然可以类似做。
剩下的中国剩余定理合并即可。

最小内向森林问题

这个是张哲宇的工作，它在左偏树优化朱刘算法的基础上进一步，得到了 $O(m\log m)$ 对每个 $x$ 求出 $x$ 条边时的最小内向森林的算法。

我们先要理解左偏树优化朱刘算法（不是暴力 $O(nm)$ 的算法）。
（我觉得这个讲得比洛谷题解好多了，理性愉悦）

两条引理：
将一个节点的所有出边同时加减，不影响最优解形态。证明考虑每条边只会选择一条出边。
如果图上所有边权非负，那么边权为 $0$ 的环可以视为一个节点。显然..
首先考虑我们如果选择每个点最小的出边恰好得到一棵树，那么一定是最优的。
这条和上面的两条引理结合起来这个算法就很好理解了。

算法流程：
首先同时加减使所有边权非负。
我们每次随便选择一个点，把它的出边同时加减使得最小边为 $0$，然后选择最小边作为出边。若此时已经选择的边形成环，那么缩成一个点。
若没有点能选择出边，那么结束。

最小内向森林问题
这个问题是一个经典带权拟阵交，其中一个独立集是把有向边看成无向边不成环，另一个独立集是每个点的出度不超过 $1$。于是可得这个问题是凸的。然后课件中是从凸优化（wqs二分，$O(n\log^2)$）开始一步步优化得到最后的算法，鉴于最后的算法也相当可以理解，而且课件中的推导也十分清楚，就直接给出最后的算法：

1. 起初有 $|V|$ 个内向树，每个内向树是一个点。
2. 令现在的边集是 $E_{now}$，记录 $ans_{|E_{now}|}=w(E_{now})$。
3. 求出现在每个内向树扩张代价。
4. 如果没有内向树可以扩张则退出。
5. 选择代价最小的内向树扩张，返回 2

其中“扩张代价”是指根的指向树外的最小边权。求的方法是不停地选择这棵树的根节点，如果最小边指向自己则执行缩环，直到指向树外，这条指向树外的边的边权。需要注意的是这时如果对根的所有出边加减的话，还不能累加到答案中，因为这棵树还有可能不扩张，我们只是先算出它的代价。
那么我们可以每合并两棵树就先执行不停缩环，就可以得到这棵合并后的树的扩张代价。然后把所有的扩张代价扔到全局的堆里，每次取出堆顶即可。

所以它比左偏树优化朱刘只多了一个全局堆来指导应该选哪个点...（在洛谷提交了，不过不知道对不对，因为没有这个板子/cy）

上海森堡矩阵

8,2员交讲了一个省选d2t3模合数的做法，十分神仙/yun。
其中提到了利用上海森堡矩阵 $O(n^3)$ 求特征多项式，可以学一学。
主要是利用 $A=PBP^{-1}$ 则 $A$ 和 $B$ 特征多项式相同的性质，然后来把原矩阵消成上海森堡矩阵来求特征多项式。
具体地，我们发现左乘初等矩阵是行初等变换，右乘是列，所以现在操作是：将第 $i$ 行乘 $c$，第 $i$ 列乘 $c^{-1}$；交换第 $i,j$ 行和第 $i,j$ 列；将第 $i$ 行的 $c$ 倍加到第 $j$ 行，将第 $j$ 列的 $-c$ 倍加到第 $i$ 列。
这些操作足够消成上海森堡矩阵。对于上海森堡矩阵，只需dp求一下行列式即可。代码

有向图的割点和桥

是8.3陈孙立的交流。
这个问题其实还是比较简单的。

考虑到有向图的强连通分量和无向图中的连通分量有类似的性质，所以可以类似定义“强割点”和“强桥”，即删去之后强连通分量数量变化的元素。
首先我们可以把边新建一个点，这样强桥就可以规约到强割点了。

考虑强连通分量和连通分量类似的性质，具有传递性。与无向图类似，我们也可以分别在每个强连通分量中求出，再并起来就是答案。
考虑删掉一个点之后图的状态，如果它还是强连通那么对图中任一个点都和其他点强连通。否则对任意一个点都能找到不能互达的点。于是可以随便挑选一个点 $x$ 来判断这样的条件，即如果 $y\neq x$ 是割点，那么会存在 $z\neq y$ 使得 $x$ 到 $z$ 的或 $z$ 到 $x$ 的路径都经过 $y$，这样删去之后才会不能互达。
于是算法就出来了：
我们先求出原图所有强连通分量，对每个分量操作，以下图都是强连通图。
在图中随便选择一个点，暴力判断一下它是不是强割点。
以这个点为源，分别在原图和反图中建出支配树，得到所有非平凡支配点，它们都是强割点，其他点都不是强割点。