louhc

题解

未归档(78)

/ 注册

全部文章 / 题解（共2篇）

题解 | 算法竞赛进阶指南可持久化并查集

思路说是可持久化并查集,实际上就是把并查集使用的数组变成可持久化数组.当然,可持久化并查集路径压缩不现实,这样可能总共需要修改个值,空间复杂度可能不好过去.想象当初学并查集时使用的优化,出了路径压缩,还有按秩合并.这样一次只需要修改个值,而且复杂度基本一样.这样子时间复杂度为,空间复杂度为. 代码...

并查集可持久化数据结构

2019-08-28

0 632

题解 | 算法竞赛进阶指南关押罪犯

思路这题可以用并查集或二分+二分图染色解决.首先二分答案,然后只要判断是否能将罪犯分成两个图,图的内部边权都不超过答案. 并查集这样子可以直接使用并查集的边带权或者扩展域解决.对边从小到大排序.边带权的话,边权可以是两点是否相同,合并时如果有冲突判断就输出答案.扩展域的话也就是每个罪犯拆成两个点...

二分并查集二分图染色

2019-08-24

0 657