拟阵交

· · 算法·理论

例题

考虑更为普遍的拟阵交算法，可以在大约 O(n^3) 复杂度内求解最大独立集或最小权独立集。

设两个拟阵分别为 M_1(E,I_1),M_2(E,I_2)。

假定我们目前已经维护出大小为 |A| 的拟阵交。考虑能否扩展得到大小为 |A|+1 的独立集。

构造图论模型，设源点 S 和汇点 T,B=E-A。考虑将 b\in B 分成两部分点。

考虑 a\in A。

跑 S 到 T 的最短增广路，把最短路径 P 上的点的状态全部取反，不难发现 |A'|=|A|+1。如果要求最小权，就增加点权DIY Tree。