点分治(Centroid Decomposition)

作者:水作自动机 分享于:2019/1/11 21:29:22
说明
操作方法: 鼠标移动节点,按空格键放置。 当你觉得放置了足够多的节点后,按f结束放置节点。 然后你可以点击两个节点,将它们之间连接一条带权的边。 注意此算法是在树上进行的,所以请确保你构造的图连通而无环。 不过为了防止产生环,当你尝试连的边会构成环时,你将无法建这条边。 当你连接了`节点个数-1`条边后,你将不能继续连边,同时算法也会开始进行。 ps:边权必须为正整数 点分治是一种可以解决大量树上路径问题的算法。 时间复杂度为:O(n log n),相比暴力的O(n^2)来说,还是很优秀的。(然而这并不能在sc中体现出来) 其中的分治方法也很巧妙,这样的模板还可以用于很多类似问题上。 甚至IOI(**I**nternational **O**lympiad in **I**nformatics)的一道题,几乎是此题的模板!由此也能发现这个算法的强大所在。 比如这个作品解决的问题是: 给定一棵无根树,树带边权。求树上有多少条简单路径的权值为k。 为了防止sc爆内存,这里k≤10^4。 不过,这里直接算出了所有简单路径的权值,并记下了各种权值的出现次数。 这里的路径指的是“有向路径”,即 u->v 和 v->u 被看做是两条不同的路径。 查看答案的方法:直接在ext数组中查看,第i项代表的就是长度为i的有向路径数量 也可以按q键来查询,来跳到ext数组中的某一项
4
73
扫一扫
303

评论 (4)

您还可以输入500个字符。
发表
取消
  • 正载入评论...