[题解] AT_wtf22_day2_d

· · 题解

1

直接做是一般图最大权匹配。暴力做，每次取出的仍然是一条增广路。此时增广路不一定是简单路径，但仍然保持边交错的性质，可以分解为简单增广路和若干简单交错路。

限制是颜色不同、w_i+w_j \le L。先考虑 w_i+w_j\le L，若不合法则有 w_i+w_j > L\Longrightarrow \max(w_i, w_j)> \frac L 2。这启发我们把点分为权值 \le \frac L 2 的小点和另外的大点。（在异色的情况下）任意一对小点都能匹配，任意一对大点都不能匹配。称小点间的匹配为小小匹配，小点-大点的匹配为小大匹配。

2

小小匹配只有异色的限制，而小大匹配有额外的权值和限制。先求出一组最优的小大匹配，再向其中加入一组小小匹配：

因此对于一组最优的的小大匹配，加入小小匹配后不会删除小大匹配点集中的任何点。 注意只是点集不变，与某个点相邻的匹配点有可能改变。

3

对于小大匹配后剩下未匹配的小点集 R，其中匹配只有异色的限制。若 R 中没有出现次数为绝对众数的颜色，则能有一组完美匹配，否则只能由该颜色的点匹配其余颜色的点。

设小大匹配后，颜色 c 剩余点数量下界为 f_c，x=|R|。我们断言，若 \exists c, 2f_c > |R|，则颜色 c 中的 2f_c-x 个点一定未匹配，剩下都能匹配；否则有一组完美匹配（若 2 \nmid x，则需要扔掉一个点）。

对第一种情况，求出一组取到绝对众数颜色的下界的小大匹配即可。

对第二种情况，求出任意一组小大匹配，设该组匹配中颜色 c 的剩余数量为 h_c。h_c 没有绝对众数就做完了。若有，设绝对众数的颜色为 c，则有 f_c\le \frac L 2 < h_c。取另一组 h'_c = f_c 的匹配，将两者边集取对称差，则能每次取一条增广路进行调整，直到 h_c\le \frac L 2 为止。

4

于是只需求小大匹配的点集。令大点点权为 A_i，小点点权为 B_j = L - w_j，则权值和的限制改写为 B_j \ge A_i。权值较大的大点可取的小点集合，包含于权值较小的大点可取集合。因此贪心即为按 A_i 从大到小枚举大点，能匹配则匹配。

用 Hall 定理快速判定大点 i 是否能在匹配中。令已扫描的大点为 L、小点为 R，则最大匹配为 |L|-\max_{S\subseteq L} \left\{ |S| - |N(S)| \right\}。新加入点 i，则 |L| 的大小增大；若要判断 i 不能使匹配大小增大，则 i\in S。往 S 中加入所有与 i 同色的点，N(S) 就包含 R 中所有与 i 异色的点。S 中最小的与 i 异色的点 j（若存在），则 N(S) 中包含了所有 B \le A_j 的点。因此选择 S 的形态为：

在加入大点、小点时维护每种 i 颜色的答案即可。这样能求出大小匹配中最优的大点集。

保留选出的大点集，反着跑一遍，能求出大小匹配中最优的小点集，这些小点必须在大小匹配中。注意这时可能需要满足第 3 部分中，某种颜色剩余点数量取下界的限制，此时需要的不再是整个小点集，而是取到下界时该颜色选的点集。剩下颜色异于该颜色的点要么在小大匹配中，要么在小小匹配（为完美匹配）中。

5

要求 f_c，只需求所有颜色为 c 的小点与所有选中大点的最大匹配。可以证明，最大化颜色为 c 的小点数量不会影响小大匹配的大小（根据贪心的过程容易说明，在有多个候选小点项时优先选择颜色 c 是可以的）。

于是最终过程为：先求 f_c 与小大匹配的大点集，再根据 f_c 绝对众数、奇偶性的限制求小大匹配的（必选）小点集，最后按 f_c 的限制丢弃一些小点。

复杂度 O(n\log n)。