sunny_forever

分类

题解(57)

/ 注册

全部文章（共4篇）

题解 | #Black and white#

B题题解队友别骂了，别骂了，我不该以为这题是最短路思路为了实现最少花费，需满足：在我们涂完若干个点后，其他的点对总花费不再有贡献（涂黑这些点时不花钱了）我们会发现：最少，我们需要涂黑 n + m - 1 个点，且涂完这些点后所有的行和所有的列会都在一个联通块里面举例如下：不妨令 n...

最小生成树 Kruskal 思维

2021-07-25

11 735

题解 | #Rinne Loves Graph#

思路求能从 1 号点到达 n 号点并且满足相关条件的最短路条件：穿过的被***城镇不能超过 K 个解法：最短路＋ dp dist[i][j]：从起点开始穿过了j个被***的城市到达i点的最短距离ps：dist 最后一定是最短距离，但中间过程的值不一定是，因为后续可能被再次更新所...

最小生成树 dp

2021-07-09

6 665

题解 | #Forsaken喜欢独一无二的树#

题意删除一些边，使得最小生成树唯一，问删除的边的权值和最小是多少？思路为什么最小生成树不唯一：因为连接相同两个集合的边，权值相同的可能有多个所以，我们只需要删除权重相同的且连接同两个集合的那些边即可：这些边中留一个用于维持最小生成树，其余的均删掉。因为是稀疏图，所以使用 Kru...

最小生成树并查集

2021-07-08

1 536

题解 | #[HAOI2006]聪明的猴子#

题意求出满足条件的猴子的数目，满足的条件是：能在这个地区的所有树冠上觅食换成用数学语言来描述条件：猴子的最大跳跃距离 MaxD 需大于或等于最小生成树边集中最长的那条边最小生成树：联通该地区所有的树冠所形成的最小生成树思路 prim 算法扫一遍，在这个过程中，求出最小生成树边...

最小生成树

2021-07-08

2 563