题面
给出一个排列 ,把每个位置视为点,建一个无向图, \(i,j\) 之间的边权为 \(|i-j|\times|p_i-p_j|\) 。求这个图的最小生成树。
数据范围:\(n\le 5\times 10^4\) 。
题解
这个题题目很好的说明了,一看到完全图最小生成树,不要只想到 B算法 。
拆一下 \(|i-j|\times|p_i-p_j|=ip_i-jp_i-ip_j+jp_j\) ,发现这个又包含了 \(ip_j\) ,也包含了 \(jp_i\) 。
所以我们得找其他方法。
这时候要注意到 \(p_i\) 是一个排列,有什么是只有排列才能满足的呢?
值域小!
再看一看就会发现:我们值考虑 \(i,i+1\) 的边 ,这样的生成树每条边边权都 \(\le n\),因此存在一种最小生成树中也只有边权 \(\le n\) 的边。
那么,可以和 \(i\) 相连的有效的边就只有 \(O(\sqrt n)\) 个,这样复杂度就优化下来了。
启发
- 完全图最小生成树,不要只想到 B算法 !!!