题解：CF1572D Bridge Club

happybob · 2025-11-10 21:36:09 · 题解

神秘题。

注意到 i,j 有边当且仅当 \mathrm{popcount}(i \oplus j) = 1，故 \mathrm{popcount}(i) 与 \mathrm{popcount}(j) 奇偶性必然不同，问题转化为 O(2^n) 个点 O(n2^n) 条边的最大权二分图匹配。

注意到每选一条边，至多使得 2n-2 条边不能再选，故只需要保留前 2nk 大条边跑最大费用流即可。这样点数边数都是 O(nk)，怎么跑都能过。