CF1572D

云浅知处 · 2024-02-14 17:02:39 · 题解

显然图是二分图。注意每个点度数不超过 2n，考虑取出前 (2n-1)(k-1)+1 大的边，我们声称最大权匹配一定在这些边中取到。

这是因为，考虑一条边最多和 2n-2 条边相邻，算上自己一共有 2n-1 条边在选上这条边之后无法再选，

所以如果取出的边中只取了不到 k 条边，目前不能选的边数至多为 (2n-1)(k-1)，因此一定有一条取出的边还可以选上，于是选上它自然比选一个未取出的更小的边更优。

这样就变成要对一个 O(nk) 个点，O(nk) 条边跑最大费用最大流的过程。注意增广只会进行 k 轮，如果使用 dij 费用流，总复杂度为 O(n2^n+n^2k^2+nk^2\log(nk))。

但注意到一开始的图是严格分成三层的 DAG，且任意时刻图中最多出现 O(k) 条负边，于是最短路长度为 O(k) 级别，spfa 的实际复杂度为 O(nk^2)。

于是 dij 费用流的实际复杂度为 O(n2^n+nk^2\log(nk))，直接 spfa 的复杂度为 O(n2^n+nk^3)，均可通过。

https://codeforces.com/contest/1572/submission/246330855