「CROI · R2」落月摇情

构造 m 条边的连通简单图,边权为 a_u a_v;先求 MST,再用排序后的点权多路归并选剩余最小边。

来源 Luogu P10768 · 标签 生成树 / Kruskal / 贪心 / 构造 / 堆

题目描述

给出 𝑛 个点,第 𝑖 个点有点权 𝑎𝑖。需要构造一张有 𝑚 条边、无重边、无自环的无向连通图。边 (𝑢,𝑣) 的权值为 𝑎𝑢𝑎𝑣,最小化所有边的权值和,并输出构造方案。

1≤𝑛≤106,𝑛−1≤𝑚≤min(106,𝑛(𝑛−1)2),|𝑎𝑖|≤106。

题解

先求完全图的 MST,再补足 𝑚−𝑛+1 条边。

把点按 𝑎𝑖 升序排序。完全图中每条边的权值是两个点权的乘积,可以按正负性分成三类:

  • 所有 𝑎𝑖≥0:所有点连向最小点。乘积随另一个点权增大而增大。
  • 所有 𝑎𝑖≤0:所有点连向最大点,也就是绝对值最小的点。
  • 同时存在正数和负数:令 𝐿 为最小点,𝑅 为最大点。连接 (𝐿,𝑅),所有负数点连向 𝑅,所有非负数点连向 𝐿。这样会取到所有可用的负权边,剩余边也由绝对值最小的端点连接。

这 𝑛−1 条边就是 MST。接下来还需要加入 𝑚−𝑛+1 条边;此时图已经连通,所以只要选当前未使用边中权值最小的即可。

不能枚举 𝑂(𝑛2) 条边。固定一个端点 𝑖 后,𝑎𝑖𝑎𝑗 关于 𝑎𝑗 是线性的:

  • 若 𝑎𝑖≥0,𝑗 从点权最小的一端向最大端移动时,乘积递增;
  • 若 𝑎𝑖<0,𝑗 从点权最大的一端向最小端移动时,乘积递增。

因此对每个点只维护一个候选指针,用最小堆做多路归并。初始把 MST 的边放进堆;每次取出最小边,如果尚未选过就加入答案,然后让对应端点沿自己的方向推进到下一个候选邻居。每条无向边只从固定端点的一侧枚举,重复边直接跳过。

堆中最多维护 𝑂(𝑛) 条候选,取满 𝑚 条边即可,总复杂度 𝑂((𝑛+𝑚)log𝑛),空间 𝑂(𝑛+𝑚)。

复杂度

排序点权为 𝑂(𝑛log𝑛),MST 构造为 𝑂(𝑛),多路归并的堆操作共 𝑂((𝑛+𝑚)log𝑛)。总复杂度 𝑂((𝑛+𝑚)log𝑛),空间 𝑂(𝑛+𝑚)。

源码位置