苟且的狮子的博客

[JSOI2010]GROUP 部落划分 GROUP

kruskai，贪心题意：分析：这一题我是由kruskai算法为突破口的。我们想想，对于一揽子的节点，我们要对他们进行并查集操作，将其合成k个集合。然后求集合间的最短距离。我们想让这个最短距离尽量大！由kruskai算法作为突破口，我们不妨对所有的边按照其权值从小到大排序。边：共有n*...

[HNOI2006]公路修建问题

最小生成树、kruskai算法题意：废话：做了些题单的题后，我发现题目考察点基本上围绕着建图、算法本身理解、dp 三点展开。本题考察的是对kruskai算法的理解分析：我们首先抓住重要信息：公路1是一定比公路2开销大的！至少要有k条公路1.那么很明显我们就只铺设k条公路1好了，剩下的都...

Forsaken喜欢独一无二的树

题意：分析：正如“jxnu-19-软技一班-刘晟”所说的，按照kruskai算法的想法来看的话，出现多条最短路径的原因只可能是存在复数的最小权值边连接着两个集合以供选择。那我们其实只要在kruskai算法进行的同时动手脚就行了。我们先对权值进行从小到大的排序，然后将其分为一个个的相等权值的集...