首页 > 黑暗城堡
开通博客写题解
头像 随随便便哈哈
发表于 2022-04-05 22:36:43
solution 最短路 + 最小生成树 ⇒\Rightarrow⇒ 最短路径生成树 题目要求很明确，求出有多少棵最短路径生成树。 关于最短路径生成树请点击[这里][8]。简要概括一下，最短路径生成树就是对于树中的任意一对父子节点 f,sf , sf,s ，diss=disf+wdis_s = di 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 随随便便哈哈
发表于 2022-04-05 22:39:04
北极通讯网络 solution 题目很抽象，简化一下就是求解一个最小的 ddd ，使得删去权值大于 ddd 的边后，剩下的联通块的个数不超过 kkk 个。可发现本题难点就在于模型的抽象，抽象出这一点来，解题不难。我们在进行 KruskalKruskalKruskal 算法时其实就是在维护图中联通块的 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 随随便便哈哈
发表于 2022-04-05 22:41:39
新的开始 前言 构建虚拟源点的方式来求解图论问题，比较常用，尤其是在负环问题和差分约束问题上更为普遍。 在最小生成树类的问题上同样有相似的应用。 solution 求解本题的关键在于办法1上，我们可以通过构建虚拟源点 0 来解决，对于每一个 iii 点，构建一条以000为起点，iii 为终点，边权为 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 随随便便哈哈
发表于 2022-04-05 22:43:46
Tree solution 求一棵恰好有 needneedneed 条白边的最小生成树，根据 MSTMSTMST 的求解方法，一条白边是否在 MSTMSTMST 中只与白边的权值有关。所以我们只需对白边进行增量操作即可。假设我们对图中的每条白边的增量为 xxx ，MSTMSTMST 中白边的数量记为 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 随随便便哈哈
发表于 2022-04-05 22:47:18
构造完全图 题意： 给你一棵树，将这棵树扩充为完全图，满足该图的最小生成树为这棵树。求边权和值最小是多少。 思路： 根据完全图的性质，每两个点都至少有一条边联通。再想 KruskalKruskalKruskal 算法的实现流程，我们只需要在合并两个单独并查集的时候，记录一下贡献就可以了。因为在 Kr 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”