CF1305G: Kuroni and Antihype

把操作转化为最大生成树,用 Borůvka + max-plus Zeta 变换(SOS DP)求最大边。

来源 Codeforces 1305 G · 难度 Codeforces 2700 · 标签 生成树 / Borůvka / Zeta 变换 / SOS DP

题目描述

有 𝑛 个数 𝑎𝑖 和一个集合 𝑆。初始时 𝑆=∅。你可以进行两种操作:

  1. 把 𝑥(1≤𝑥≤𝑛)加入 𝑆,没有奖励。
  2. 选择 𝑆 中的一个数 𝑥 和不在 𝑆 中的一个数 𝑦,且 𝑎𝑥and𝑎𝑦=0,把 𝑦 加入 𝑆,奖励为 𝑎𝑥。

要求把 1,2,…,𝑛 都加入 𝑆,求最大化的奖励和。

1≤𝑛≤2×105,0≤𝑎𝑖≤2×105。

题解

设 𝑎0=0,一开始 𝑆 中有 0。那么所有的 1 操作都可以转化为 𝑥=0 的 2 操作。

容易发现,所有的 2 操作构成一棵以 0 为根的有根树。

设树上节点 𝑖 的度为 𝑑𝑖。那么奖励为

∑𝑖=0𝑛(𝑑𝑖−1)𝑎𝑖

注意到

∑𝑖=0𝑛(𝑑𝑖−1)𝑎𝑖=∑𝑖=0𝑛𝑑𝑖𝑎𝑖−∑𝑖=0𝑛𝑎𝑖

因此只需要最大化 ∑𝑖=0𝑛𝑑𝑖𝑎𝑖。

这等价于在加权无向图 𝐺=(𝑉,𝐸) 中求最大生成树的边权和:

  • 顶点集为 0,1,…,𝑛;
  • 边集为所有满足 0≤𝑖<𝑗≤𝑛 且 𝑎𝑖and𝑎𝑗=0 的点对 (𝑖,𝑗);
  • 边权为 𝑤(𝑖,𝑗)=𝑎𝑖+𝑎𝑗。

用 Borůvka 算法求最大生成树。每轮需要为每个连通块找一条权值最大的出边。

记 𝑐𝑥 为满足 𝑦and𝑥=𝑦 且 𝑎𝑦 最大的 𝑦,𝑑𝑥 为次大的、且与 𝑐𝑥 不在同一连通块的 𝑦。

这等价于在布尔格上做 max-plus Zeta 变换(SOS DP):计算

𝐶(𝑥)=max𝑦⊆𝑥𝑎𝑦

同时维护子集内来自不同连通块的前两名,就能得到 𝑐𝑥 和 𝑑𝑥,于是可以 𝑂(1) 为每个点找到最优出边。

复杂度

每轮重建 Zeta 表的代价是 𝑂(𝑊log𝑊),Borůvka 共 𝑂(log𝑛) 轮,总复杂度 𝑂(𝑊log𝑊log𝑛),其中 𝑊=218 为值域,空间 𝑂(𝑊)。

参考

源码位置