Tag Archives: Kruskal

[双连通分量+树上倍增+并查集+Kruskal]51nod1743雪之国度

Cptraser/ 十月 29, 2018/ 2018.10/ 0 comments

[51nod1743]雪之国度 雪之国度有N座城市,依次编号为1到N,又有M条道路连接了其中的城市,每一条道路都连接了不同的2个城市,任何两座不同的城市之间可能不止一条道路。 雪之女王赋予了每一座城市不同的能量,其中第i座城市被赋予的能量为。 如果城市u和v之间有一条道路,那么只要此刻雪之女王的能量不小于,这条道

Read More

初涉Kruskal重构树

Cptraser/ 十月 29, 2018/ 2018.10/ 0 comments

初涉Kruskal重构树 一种贼牛逼的思路,本来NOI之后就想学的,但一直到现在才学习… 考虑下面这个问题:给定一个无向连通图,求路径上的最小值。 我会树连剖分!! 可以用重构树解决,代码复杂度和常数大大下降。 (从小到大)将边权看成一个新点,将它与路径两点集合以父子关系连边。 这是核心过程:(新建节

Read More