随随便便哈哈

分类

题解(5)

/ 注册

全部文章（共5篇）

题解 | #构造完全图#

构造完全图题意：给你一棵树，将这棵树扩充为完全图，满足该图的最小生成树为这棵树。求边权和值最小是多少。思路：根据完全图的性质，每两个点都至少有一条边联通。再想 KruskalKruskalKruskal 算法的实现流程，我们只需要在合并两个单独并查集的时候，记录一下贡献就可以了。因为在 Kr...

C++

2022-04-05

1 365

题解 | #Tree#

Tree solution 求一棵恰好有 needneedneed 条白边的最小生成树，根据 MSTMSTMST 的求解方法，一条白边是否在 MSTMSTMST 中只与白边的权值有关。所以我们只需对白边进行增量操作即可。假设我们对图中的每条白边的增量为 xxx ，MSTMSTMST 中白边的数量记为...

C++

2022-04-05

1 246

题解 | #新的开始#

新的开始前言构建虚拟源点的方式来求解图论问题，比较常用，尤其是在负环问题和差分约束问题上更为普遍。在最小生成树类的问题上同样有相似的应用。 solution 求解本题的关键在于办法1上，我们可以通过构建虚拟源点 0 来解决，对于每一个 iii 点，构建一条以000为起点，iii 为终点，边权为...

2022-04-05

1 272

题解 | #北极通讯网络#

北极通讯网络 solution 题目很抽象，简化一下就是求解一个最小的 ddd ，使得删去权值大于 ddd 的边后，剩下的联通块的个数不超过 kkk 个。可发现本题难点就在于模型的抽象，抽象出这一点来，解题不难。我们在进行 KruskalKruskalKruskal 算法时其实就是在维护图中联通块的...

C++

2022-04-05

1 292

题解 | #黑暗城堡#

solution 最短路 + 最小生成树 ⇒\Rightarrow⇒ 最短路径生成树题目要求很明确，求出有多少棵最短路径生成树。关于最短路径生成树请点击[这里][8]。简要概括一下，最短路径生成树就是对于树中的任意一对父子节点 f,sf , sf,s ，diss=disf+wdis_s = di...

C++

2022-04-05

2 299