堆优prim的通常写法和kruskal时间复杂度一样，常数还更大
如果你堆优prim想比kruskal快那要用优秀的堆
~~这题n才5000，说不定不加堆优反而会快？~~
by 142857cs @ 2020-08-11 14:33:42
@[gxy001](/user/55707) 你别乱说啊
by 142857cs @ 2020-08-11 14:34:07
prim是$O(n^2)$
kruskal是$(m log m)$
~~好像把~~
by WZKQWQ @ 2020-08-11 14:35:15
@[WZKQWQ](/user/239433) 你那是不加堆优化的prim
堆优化prim是O(mlogn)，或者用斐波那契堆是O(m+nlogn)
by 142857cs @ 2020-08-11 14:36:35
嘤嘤嘤被大佬吊打
by WZKQWQ @ 2020-08-11 14:37:15
@[142857cs](/user/35760) 堆优```prim```的复杂度不是 $ O(m\log_2n) $ 吗
by Magallan_forever @ 2020-08-11 14:37:19
@[142857cs](/user/35760) 时间复杂度不一样，prim时间复杂度基于点数，稠密图更快，kruskal基于边数，稀疏图更快
by gxy001 @ 2020-08-11 14:37:51
@[AT是女孩子](/user/157598) 是啊，kruskal也是这个复杂度啊
by 142857cs @ 2020-08-11 14:37:52
~~评测姬波动，我刚刚交题两次UKE，建议重交~~
by 时律 @ 2020-08-11 14:39:14
@[142857cs](/user/35760) ```kruskal```是 $ O(m\log_2m) $吧
by Magallan_forever @ 2020-08-11 14:39:35