Luogu P1265 公路修建

一眼看去，就是一道MST的模板题。 然后果断准备跑Kruskal，然后5个TLE。 Kruskal复杂度对于这个完全图要O(n^2*logn^2),快排就会导致超时。 然后打了刚学的Prim。朴素O(n^2）卡过。 Prim的思想很简单，用dis数组来存目前的MST（初始时只有一个节点）到其他点的最
posted @ 2017-11-30 19:23  空気力学の詩  阅读(209)  评论(0)  编辑  收藏  举报