[题解] 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

的形态为：

决策某个颜色 $c$ ，该颜色在 $R$ 中最小权值为 $A_k$ ， $S$ 包含 $R$ 中 $\ge A_k$ 的前缀。
$S$ 额外包含 $< A_k$ 的所有与 $i$ 同色的点。
小点的形态已由此确定，也为一段前缀、一段异色点。

在加入大点、小点时维护每种

i

颜色的答案即可。这样能求出大小匹配中最优的大点集。

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

5

要求

f_c

，只需求所有颜色为

c

的小点与所有选中大点的最大匹配。可以证明，最大化颜色为

c

的小点数量不会影响小大匹配的大小（根据贪心的过程容易说明，在有多个候选小点项时优先选择颜色

c

是可以的）。

于是最终过程为：先求

f_c

与小大匹配的大点集，再根据

f_c

绝对众数、奇偶性的限制求小大匹配的（必选）小点集，最后按

f_c

的限制丢弃一些小点。

复杂度

O(n\log n)

。

[题解] AT_wtf22_day2_d

文章操作

1

2

3

4

5

相关推荐

评论

[题解] AT_wtf22_day2_d