我记得kruskal的复杂度主要是sort
~~你可以手写快排~~
by WZKQWQ @ 2020-08-11 14:42:20
@[WZKQWQ](/user/239433) ~~手写快排比STL里的不退化sort要慢~~
by 时律 @ 2020-08-11 14:42:56
@[gxy001](/user/55707) 你自己不懂就不要乱说好不好
“kruskal适用于稀疏图”是指不加堆优化的prim和kruskal的比较，堆优化的prim和kruskal复杂度相同（kruskal的瓶颈在排序，除非你用基数排序）
prim的时间复杂度也不是O(nlogn)，你读入就不止O(nlogn)
而且这题不是稀疏图
by 142857cs @ 2020-08-11 14:43:40
~~我感觉会出神贴~~
by 绝顶我为峰 @ 2020-08-11 14:44:11
@[AT是女孩子](/user/157598) mlogn和mlogm是相同的时间复杂度
by 142857cs @ 2020-08-11 14:44:21
@[AT是女孩子](/user/157598) 为什么我看不了你的代码/dk
by Semsue @ 2020-08-11 14:45:27
我记得稠密图中$n^2$dij比堆优化还快
by Semsue @ 2020-08-11 14:46:01
@[Flying_Bird](/user/328405)
~~你没A（滑稽）~~
你没开公开计划。
by WZKQWQ @ 2020-08-11 14:46:47
@[Flying_Bird](/user/328405) 确实，不过这题也不是稠密图？
by 142857cs @ 2020-08-11 14:46:51
这题应该算个不稀不密的图吧（
by 时律 @ 2020-08-11 14:48:14