boruvka算法

摘要:
它用于解决一些特殊的mst问题。对于每个集合,维护一个trie来表示集合中的所有数字。然后要求整个trie减去集合trie的最小XOR和。设(d_x)表示从点(x)到重心的距离。y) (p_x+p_y)的成本可以表示为(p_x+p_y)。很容易发现,只要我们找到(p_x)的最小值的位置(y),就可以考虑如何确定一个点是否可以展开。预处理的输出(f_s)表示具有(s)的集合中的方向,可以在恒定时间*(O(n))内进行预处理。

一个mst算法。
其用于求解一些特殊的mst问题。
例题1:CF888F
我们要求一个集合到外面的最小边。
对于每个集合维护一个trie表示这个集合内的所有数。
维护一个整体trie,表示所有数。
对于每个集合,枚举这个集合的所有点。然后询问整体trie减去这个集合trie的最小异或和即可。
时间复杂度(O(nlog_2^2n))
当然还有一个做法:考虑按位分治。把高位为(1,0)的都递归下去,然后询问两个集合的最小异或和。
例题2:at3611
考虑直接套用boruvka算法。
考虑树上dp。
每个点要记录最大值,与最大值颜色不同的次大值。
然后这样子就能求出和一个点距离最近的点。
然后就能用boruvka了。
另一个做法:把所有边集做若干次mst,排除一定不会选择的边。
然后全局做一个mst,答案不变。
考虑点分,考虑跨越重心的路径。
(d_x)表示(x)点到重心的距离。
则我们两个点(x,y)的点权可以被表示成(d_x+a_x+d_y+a_y)
(p_x=d_x+a_x),则连接两个点(x,y)的代价可以被表示成(p_x+p_y)
容易发现只要我们求出(p_x)的最小值位置(y),把所有点和(y)连边。
这样子就把跨过分治中心的路径的mst求出来了。
然后最后做一次mst即可。
例题3:病毒实验
其实这道题不是boruvka。但是运用了这个算法的思想。
考虑我们怎么判定一个点是否能被拓展。预处理出(f_s)表示有(s)集合内的方向,最长连续段的长度。
可以在常数时间*(O(n))内预处理。
考虑把矩阵划分成若干个连通块,每个连通块内有一关键点(c)。从连通块任意点都能拓展到(c)
一个显然的性质:如果一个连通块关键点(b)能够走到(c),那么(b)所在连通块不能用于更新答案。
考虑使用这个性质进行bfs。可惜对时间复杂度没有改进。
考虑boruvka算法的时间复杂度证明。
每次给一个连通块通过bfs找到其不在连通块的出边。
然后把它和这个出边所指向的连通块合并。
如果bfs到一个已经被合并的区域就跳出,不用bfs了
可以发现时间复杂度是(O(RClog_2 RC))
会发现一个点到的合并只有两种:
1.和一个区域合并。
2.bfs到一个被合并过的区域。
会发现1情况使两个连通块变成一个,2情况使一个连通块变成(0)个。
所以时间复杂度有保证。
例题4:lg6199
考虑在(T2)上进行树分治。
(d_x)表示(x)到重心的距离。
连接两个点的代价就是(d_x+d_y+T1dis(x,y))
建立连通块在(T1)上的虚树,就转化成例题2了
例题5:https://www.cnblogs.com/ctmlpfs/p/14333369.html

免责声明:文章转载自《boruvka算法》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇Markdown列表中嵌套代码带来的问题Eclipse中没有Plug-in Development 或 Plug-ins选项(转)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

借助AWR报告分析解决oracleCPU过高的问题(转)

原文地址:http://www.cnblogs.com/crystal-guoguo/p/4213458.html 简介:在oracle数据库中,有两个非常实用的自带监控工具EM(Enterprise Manager)和AWR(Automatic Workload Repository)。其中,通过AWR报告可以生成易于阅读的监控报告,可协助进行性能问题的...

rsync常用命令及格式

rsync在同步文件夹内容这个工作上应用非常广泛,但是rsync本身命令还是比较复杂,本文总结一下: rsync = remote sync的简称 ,它 被用于在linux/unix系统中执行备份操作。rsnync用于从一个位置到另外一个位置同步文件和文件夹。备份的地址可以是本地也可以是remote server。 rsync的重要功能: speed 首次...

CCF-201512-3-画图

问题描述 试题编号: 201512-3 试题名称: 画图 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   用 ASCII 字符来画图是一件有趣的事情,并形成了一门被称为 ASCII Art 的艺术。例如,下图是用 ASCII 字符画出来的 CSPRO 字样。   ..____.___...

SQLServer根据时间段查询数据

今天一同事发现一个SQLServer语句执行特别慢,检查后发现是 条件 加上了 时间段 ,之前使用的是  时间字段 between xxx and xxx这样的方式,遂更改时间判断方法, ----------dafediff----------返回两个时间点的差,可选单位 yy,mm,dd,hh,ss等 查询今年的数据  : select * from d...

大话数据结构之一(绪论、算法)

数据结构绪论 数据结构是相互之间存在一种或多种特定关系的数据元素的集合 程序设计=数据结构+算法 数据结构事实上就是一门研究非数值计算的程序设计问题的操作对象,以及它们之间的关系和操作等相关问题的学科。 数据是描述客观事件的符号,是计算机中可以操作的对象,是能被计算机识别,并输入能计算机处理的符号集合,也就是说数据必须具备两个前提: 可以输入到计...

Clickhouse TTL的那些事

TTL简介 ClickHouse原生支持数据生命周期(TTL)管理的功能 TTL即Time To Live,表示数据的存活时间。在MergeTree中,可以为某个列字段或者整张表设置TTL。当时间达到时,若列字段级别的TTL则会删除这一列的数据;若表级别的TTL则会删除整张表的数据;若同时设置了列级别的和表级别的TTL则以先到期的为准。 无论列级别还是表级...