题目描述
给定一棵 $N$ 个节点的树,要求增加若干条边,把这棵树扩充为完全图,并满足图的唯一最小生成树仍然是这棵树。
求增加的边的权值总和最小是多少。
如何连接成一个完全图?
这里采用一个方法。
-
每次找到两个点的集合
-
连接他们
-
把他们合并成一个点的集合
如何连接才能构成完全图? 完全图指的是图中任意两点都相连
把两个集合里的点都接上就好了。
举个例子 假设一个点集的大小为 $Size[a]$ 另一个为$Size[b]$
那么花 $(Size[a]×Size[b]-1)×$需要的距离就好了 减一是因为原图中被连了
我们可以不用那么麻烦 可以用并查集把两个集合合并
那么如果两个集合是已经被合并的话就没事了。
这里可以想到Kruskal算法
每次肯定是将距离最小的两个集合合并 不然有可能会被其他集合更新
乘的距离是什么距离?
乘的距离应该是使图成为完全图而不改变唯一的最小生成树的距离
因为不改变最小生成树:所以肯定不能小于$w[i]$吧
因为是唯一的最小生成树:所以肯定不能等于$w[i]$吧
那 $w[i]+1$ 就好了。
如果是 $w[i]+1$ 的话肯定不会破坏最小生成树
因为能走 $w[i]+1$ 为什么不能走 $w[i]$ 呢。
那就结束了。
题解不应该有代码的吗?