2.27 二分图与网络流复习

可能会有一些有一点用的 trick 的整理与复习。很少，很不系统。

1 Dinic 优化

• 给 bfs 和 dfs 加上当前弧优化。但是此时要一定注意在遍历时，\(rest=0\) 退出循环需要在循环内写，而非在 for 中的条件写。

• 对边权排序后分段。Dinic 很多时候慢是因为边权差距太大了。于是我们不断设一个 \(\lim\)，从 \(\max\) 开始，不断除以一个 \(c\)，然后每次加入边权 \(\ge lim\) 的边，跑一次 Dinic。在 \(c=2\) 的时候似乎复杂度可证明是 \(O(nm\log )\) 的。但是实际上 \(c\) 大一点反而更快。

• 先对只加正向边，然后对所有正向边跑（注意此时仍然要把反向边的流量给加上去）。跑完之后再加入所有反向边跑。

• 不要使用前向星。

个人认为上述东西不是很有用。如果正常考到应该无法使用上述方法获得更高的分数。

https://loj.ac/s/2015257

2 二分图独立集与覆盖集

• 点覆盖为：用点覆盖边

• 二分图最大匹配等于最小点覆盖，下面给出构造：

  1. 找到一组匹配
  2. 找到所有未匹配的左部点
  3. 从它们出发，跑增广路
  4. 未访问的左部点与访问的右部点构成最小点覆盖
  5. 大概的理解：对于匹配边两侧恰好只有一个被选，且每条边都被覆盖了。

• 二分图的最大独立集，为最小点覆盖的补集

• 二分图的最小边覆盖（无孤立点）大小，为最大独立集大小，下面给出构造：

  1. 所有匹配边全选
  2. 所有未匹配点随便选一条边

• 最长反链与最小链覆盖

  1. 考虑拆点后，out 为左部点，in 为右部点，于是 \(u\to v\) 可以连边 \((out_u,in_v)\)
  2. 于是在最大匹配上的边即在链上的边，所以最小链覆盖等于 \(n-\) 最大匹配。
  3. 根据 Dilworth 那套理论，我们求出传递闭包后，最长反链等于最小链覆盖。构造只要选出 in 与 out 都属于最大独立集即可。

3 最小割可行边与必经边

• 时间复杂度十分充裕的时候：每条边都删掉/强选跑一跑即可

• 考虑保留所有容量非 \(0\) 的边作为残量网络 \(G'\)

• 最小割可行边：原图满流，且 \(G'\) 不存在 \(u\to v\) 路径

• 最小割必经边：原图满流，且 \(G'\) 存在 \(s\to u\) 与 \(v\to t\) 的路径

• 实现方法：对 \(G'\) 跑 SCC，由于逆向边存在，所以只需要判断是否在同一 SCC 即可。

4 二分图博弈

• 匹配可行边：为匹配边，或 \(u,v\) 在同一 SCC

• 匹配必经边：为匹配边，且 \(u,v\) 不在同一 SCC

• 匹配必经点：为匹配点，且与该部的源不属于同一 SCC

• 先手必胜点，一定为匹配必经点：先手只要不断沿着匹配边走即可，而后手无法逆转

5 上下界网络流

• 大体思路：对于每个点，考虑入边 \(\sum l_e\) 与出边 \(\sum r_e\)。如果 \(\sum l_e\) 大，那么就从新源点 \(S'\) 向这个点连 \(\sum l_e-\sum r_e\) 的边，否则就连向新汇点。然后就能以 \(r_e-l_e\) 建剩余的边了。

• 无源汇可行流这样就能跑了，只需要源汇连接的满流即意味着流量平衡。

• 有源汇考虑源汇可以不守恒，那么只需要建一条原汇到原源的 \(\infty\) 的边即可。

• 考虑限制最大流。我们在新图上跑可行流，然后得到残量网络。由于已经满足流量限制，所以我们直接再在残量网络上跑 原源到原汇的流，加到答案上即可。

• 考虑限制最小流。其实差不多，只不过我们要改成退流，即跑原汇到原源的流，然后从答案中减去即可。