这篇题解的返回信息说是数学公式外使用全角公式 。请问为什么
**思路构想**:这道题是每两个点之间计算最小权值和,所以我们很容易想到**最小生成树**。
**如何实现**:我们知道传输一共有两种形式。
第一种是耗费这个文件与那个文件不同的字符数 $\times w$ 个,我们可以通过**循环**朴素地建边。
而第二种是**直接传输**,耗费 $n \times m$ 个,解决这个问题有很多种解法,这里我采用的是建立**原点**,将每个点都连接原点权值为 $n \times m$。为什么是正确的呢?我们来简单证明一下:若现在有两个点,这两点按照方案一要的字符数远大于方案二,而我们跑最小生成树的时候早就用 $n \times m$ 或更小的权值将这两个点直接或间接连一起了,所以这个方法是正确的。
建完了图,我们就可以在上面跑最小生成树了,我们在并查集的合并的时候可以**累加权值**,这样答案就出来了。
什么?你问方案怎么输出?我们可以合并并查集的时候建一个图,这个肯定是个树了,然后按照**前序遍历**输出即为步骤。