喵仔牛奶 @ 2023-07-19 16:53:02
如题，右部点有点权，最大化点权，不要求完美匹配。
最好可以做到什么复杂度？
by luogubot @ 2023-07-19 17:00:48
@喵仔牛奶 如果边数 m 是 O(n^2) 级别且权都是 1，那么可以做到 O(n^3)。
by luogubot @ 2023-07-19 17:02:02
具体地，按照右部点的点权从大到小加入 x，每次只需要判断有没有 S\to x 的增广路，每次成功增广之后/过程开始之前重新搜一遍图。
by luogubot @ 2023-07-19 17:04:17
哦看错了，是 O(n(n+m)) 的。