[HDU5398] GCD Tree(LCT)

发布于 2018-01-24  23 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU5398] GCD Tree(LCT)

Description

Teacher Mai has a graph with n vertices numbered from 1 to n. For every edge(u,v), the weight is gcd(u,v). (gcd(u,v) means the greatest common divisor of number u and v).
You need to find a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is maximized. Print the total weight of these edges.

Http

HDU

Tag

LCT

题目大意

给定一个\(n\)个点的完全图,两点之间的边的边权为两点的\(gcd\),求最大生成树

解决思路

首先肯定是不能把边都建出来的,所以考虑动态加边。但有一些边是完全没有必要的,一个点只向它的因数连边,因为非因数的边不会更优,这样就把加边的数量降到\(O(n\sqrt{n})\)。
如何动态维护最大生成树呢?我们每加入一条边,它的两端点必然已经在树中有一条路径相连啦,那么找出这条路经上的最小边,如果这个最小边小于要加入的边权,那么删除着一条最小边而插入新的这一条边。
为了维护路径上的最小边编号,我们可以把边变成点插入\(LCT\),这个点的点权即为边权,而真正的点的点权为无限大。在\(LCT\)中维护一个\(mnid\),表示最小的边权的编号。那么每次找到这样的一个点代表的边,删掉这一条边即可。
但由于\(LCT\)中会变化点与点的位置关系,所以为了方便删除边,我们要在加边的时候记录它真实连着的是哪个点,这样就可以直接删除啦。
最后需要注意的是,因为边数有\(On\sqrt{n})\),而实际上是开不了这么大的,但考虑到在任意时刻,生成树中最多只有\(n-1\)条,所以实际有用的边只有\(O(n)\)个,所以可以考虑重复使用,用一个栈作为垃圾栈,存放当期空出来的编号,每次新建点的时候,优先从这个栈中取即可。
请注意常数因子对程序时间效率的影响。另:由于只有合并操作,查找两个点是否在统一联通快可以用并查集,减少\(findroot\)的时间开销。在一些地方可以不\(Update\)

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU5398] GCD Tree(LCT)


HNCJ OIer 一枚