构造完全图 题意： 给你一棵树，将这棵树扩充为完全图，满足该图的最小生成树为这棵树。求边权和值最小是多少。 思路： 根据完全图的性质，每两个点都至少有一条边联通。再想 KruskalKruskalKruskal 算法的实现流程，我们只需要在合并两个单独并查集的时候，记录一下贡献就可以了。因为在 KruskalKruskalKruskal 合并两个并查集的时候只是保留了一条边权最小的边使两个单独的联通块 ZZZ 和 YYY 联通。所以如要构成完全图，根据乘法原理，每次操作的贡献就为 SZ∗SY−1\large S_Z * S_Y - 1 SZ​∗SY​−1 ，S\large SS 为联通块中节...

Tree solution 求一棵恰好有 needneedneed 条白边的最小生成树，根据 MSTMSTMST 的求解方法，一条白边是否在 MSTMSTMST 中只与白边的权值有关。所以我们只需对白边进行增量操作即可。假设我们对图中的每条白边的增量为 xxx ，MSTMSTMST 中白边的数量记为 f(x)f(x)f(x) ，可以易看出 f(x)f(x)f(x) 的大小是随 xxx 的增大而增大的，满足单调性，考虑二分增量。 那么这道题就可以切了。。。 code using Simon O_O ; int n , m , need , ans ; struct node { int fr...

新的开始 前言 构建虚拟源点的方式来求解图论问题，比较常用，尤其是在负环问题和差分约束问题上更为普遍。 在最小生成树类的问题上同样有相似的应用。 solution 求解本题的关键在于办法1上，我们可以通过构建虚拟源点 0 来解决，对于每一个 iii 点，构建一条以000为起点，iii 为终点，边权为 viv_ivi​ 的边。经过这样的处理，我们就可以构建出一张图，然后在图上跑最小生成树求解答案即可。 code #include <cstdio> #include <vector> #include <cstring> #include <iostrea...

北极通讯网络 solution 题目很抽象，简化一下就是求解一个最小的 ddd ，使得删去权值大于 ddd 的边后，剩下的联通块的个数不超过 kkk 个。可发现本题难点就在于模型的抽象，抽象出这一点来，解题不难。我们在进行 KruskalKruskalKruskal 算法时其实就是在维护图中联通块的个数。在每次和合并并差集的时候联通块的数量减一。所以我们只需要在求解 MSTMSTMST 的过程中记录一下合并的次数即可，当合并次数恰好为 n−kn-kn−k 时，此时加入的树边的权值就为 ddd 。 code #include <bits/stdc++.h> #define mk ma...

solution 最短路 + 最小生成树 ⇒\Rightarrow⇒ 最短路径生成树 题目要求很明确，求出有多少棵最短路径生成树。 关于最短路径生成树请点击[这里][8]。简要概括一下，最短路径生成树就是对于树中的任意一对父子节点 f,sf , sf,s ，diss=disf+wdis_s = dis_f + wdiss​=disf​+w ， www 为（f , s) 边的权值。所以针对此题来说，我们完全可以先求出起点到各个节点的最短路路径和 disidis_idisi​ ,然后暴力的去枚举每个节点，枚举这个节点连出的所有边，如果满足 diss=disf+wdis_s = dis_f + wd...