堆优化的复杂度是mlogm 相当于堆优化的dij
那为啥不用克鲁斯卡尔。。复杂度一样 常数小得多
by Rorshach @ 2018-09-05 11:47:18
@[Rorshach](/space/show?uid=59303) 不不不 prim的复杂度是可以优化到$O(n\log n +m)$的 而kruskal只能是$O(m\log n)$
by Mr_Spade @ 2018-09-05 12:21:07
@[Rorshach](/space/show?uid=59303) qwq 这个写法是我根据某算法讲堂学的. 其实这题有人用prim写的比kruskal还快 也是一样加heap. 还没细看他的代码 但是感觉应该是我写的哪里不对 毕竟差的太多了 我这个6000 他的300+ms....
by Chino @ 2018-09-05 12:24:05
@[Mr_Spade](/space/show?uid=7253) 哪里有这个科技啊我想去看看。。
@[Chino](/space/show?uid=64075) 我不会啊T_T 跑了300+ms的估计是楼上说的nlogn的办法吧
by Rorshach @ 2018-09-05 12:50:31
@[Rorshach](/space/show?uid=59303) qwq 刚写了个n^2的prim 跑了1000多ms 上面写的prim+heap跑6000 至今没懂上面那个写法哪里有问题 准备看看别人怎么写成300的好了
by Chino @ 2018-09-05 12:57:27
@[Chino](/space/show?uid=64075) 您这个……明显是mlog的啊。。
by Rorshach @ 2018-09-05 13:02:12
@[Rorshach](/space/show?uid=59303) 用配对堆或者斐波那契堆来优化就好了 也可以用pb_ds
by Mr_Spade @ 2018-09-05 13:06:30
@[Mr_Spade](/space/show?uid=7253) 直接decrease么？
那这么说 斐波那契堆难道不是O(n+m)吗？ decrease的复杂度是O(1)的
还有 配对堆的decrease怎么写啊……求教
by Rorshach @ 2018-09-05 13:16:50
@[Chino](/space/show?uid=64075) 能把那个prim+heap的代码放上来看一下么
by Rorshach @ 2018-09-05 13:20:41
pop是均摊$O(\log n)$的啊...
配对堆的decrease我也不是很清楚啊 和斐波那契堆一样就好了吧 QAQ
by Mr_Spade @ 2018-09-05 13:21:25