「CROI · R2」落月摇情
构造 m 条边的连通简单图,边权为 a_u a_v;先求 MST,再用排序后的点权多路归并选剩余最小边。来源 Luogu P10768 · 标签 生成树 / Kruskal / 贪心 / 构造 / 堆
题目描述
给出 个点,第 个点有点权 。需要构造一张有 条边、无重边、无自环的无向连通图。边 的权值为 ,最小化所有边的权值和,并输出构造方案。
,,。
题解
先求完全图的 MST,再补足 条边。
把点按 升序排序。完全图中每条边的权值是两个点权的乘积,可以按正负性分成三类:
- 所有 :所有点连向最小点。乘积随另一个点权增大而增大。
- 所有 :所有点连向最大点,也就是绝对值最小的点。
- 同时存在正数和负数:令 为最小点, 为最大点。连接 ,所有负数点连向 ,所有非负数点连向 。这样会取到所有可用的负权边,剩余边也由绝对值最小的端点连接。
这 条边就是 MST。接下来还需要加入 条边;此时图已经连通,所以只要选当前未使用边中权值最小的即可。
不能枚举 条边。固定一个端点 后, 关于 是线性的:
- 若 , 从点权最小的一端向最大端移动时,乘积递增;
- 若 , 从点权最大的一端向最小端移动时,乘积递增。
因此对每个点只维护一个候选指针,用最小堆做多路归并。初始把 MST 的边放进堆;每次取出最小边,如果尚未选过就加入答案,然后让对应端点沿自己的方向推进到下一个候选邻居。每条无向边只从固定端点的一侧枚举,重复边直接跳过。
堆中最多维护 条候选,取满 条边即可,总复杂度 ,空间 。
复杂度
排序点权为 ,MST 构造为 ,多路归并的堆操作共 。总复杂度 ,空间 。