回归梦想的博客

E2. Daleks' Invasion (medium)

题意：ｎ个点，ｍ个边，生成一个最小生成树，问对于不在最小生成树的边将其边权最大改为多少后，最小生成树可以包含该边输出ｍ－（ｎ－１）个答案如果ｎ＝＝ｍ－１的话，不需要输出任何东西题解：这个题和CodeForces - 609E 是完全一样的，就是输出不一样，换了问法，代码改改就能过题解链接对于不...

CodeForces - 609E Minimum spanning tree for each edge

题意：有个无向图，问在必选第i条边的情况下，最小生成树是多少？i会枚举每一个边题解：最小生成树好求，Kruskal即可我们记录最小生成树的值为len对于边(u,v),如果(u,v)是最小生成树的边，那直接输出答案len如果不是的话，我们就要去掉最小生成树中从u到v的路径上权值最大的边mlen，...

最小生成树(模板)

@[TOC]昨天做蓝桥杯的题，最后一题最小生成树，但好久没用一下子生疏了。。。又过了几天离散学到了最小生成树。。。趁此复习一波最小生成树两种方法：Prim和Kruskal 关于时间复杂度： prim:该算法的时间复杂度为O(n2)。与图中边数无关，该算法适合于稠密图。 kruskal:需要对图的边...