关于二分图

学术版

喵仔牛奶 @ 2023-07-14 07:58:38

  • 动态加边每次求最大匹配最好可以做到什么复杂度？
  • 求最大匹配方案数最好可以做到什么复杂度？

by Infter @ 2023-07-14 08:03:36

第二个问题建图跑dinic，好像是 O(\sqrt n m)的

by syzf2222 @ 2023-07-14 08:11:57

@喵仔牛奶 如果都在是二分图的前提下，加边的话跑流应当是 O(n+m) 的，方案数求不了。

by W_s_W @ 2023-07-14 08:18:05

@喵仔牛奶 没优化的匈牙利算法似乎是指数或者阶乘级的 \mathtt{qwq}

by Y2hlbnlpa2Fp @ 2023-07-14 08:24:38

最大匹配方案数应该是 NP 吧（

|