CF1305G: Kuroni and Antihype
把操作转化为最大生成树,用 Borůvka + max-plus Zeta 变换(SOS DP)求最大边。来源 Codeforces 1305 G · 难度 Codeforces 2700 · 标签 生成树 / Borůvka / Zeta 变换 / SOS DP
题目描述
有 个数 和一个集合 。初始时 。你可以进行两种操作:
- 把 ()加入 ,没有奖励。
- 选择 中的一个数 和不在 中的一个数 ,且 ,把 加入 ,奖励为 。
要求把 都加入 ,求最大化的奖励和。
,。
题解
设 ,一开始 中有 。那么所有的 1 操作都可以转化为 的 2 操作。
容易发现,所有的 2 操作构成一棵以 为根的有根树。
设树上节点 的度为 。那么奖励为
注意到
因此只需要最大化 。
这等价于在加权无向图 中求最大生成树的边权和:
- 顶点集为 ;
- 边集为所有满足 且 的点对 ;
- 边权为 。
用 Borůvka 算法求最大生成树。每轮需要为每个连通块找一条权值最大的出边。
记 为满足 且 最大的 , 为次大的、且与 不在同一连通块的 。
这等价于在布尔格上做 max-plus Zeta 变换(SOS DP):计算
同时维护子集内来自不同连通块的前两名,就能得到 和 ,于是可以 为每个点找到最优出边。
复杂度
每轮重建 Zeta 表的代价是 ,Borůvka 共 轮,总复杂度 ,其中 为值域,空间 。