6math6

分类

/ 注册

全部文章（共1篇）

Xor-MST（xor最小生成树）

题目：个点的无向完全图，每个点有点权，边权是点权的值。问最小生成树边权和。做法：最小生成树，经典老题了。做法是字典树上启发式合并。字典树上，按在左在右顺序，从左到右叶子表示的数的大小是有序的。所以我们先对点权从小到大排序，然后依次插入字典树上。这样字典树的子树下表示的数都来自原数组的一段连续...

01trie

2020-10-23

4 1043