萌新求助题解审核
  • 板块灌水区
  • 楼主xmxh
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/12/23 10:12
  • 上次更新2023/12/23 12:20:56
查看原帖
萌新求助题解审核
999995
xmxh楼主2023/12/23 10:12

这篇题解的返回信息说是数学公式外使用全角公式 。请问为什么

**思路构想**:这道题是每两个点之间计算最小权值和,所以我们很容易想到**最小生成树**。

**如何实现**:我们知道传输一共有两种形式。

第一种是耗费这个文件与那个文件不同的字符数 $\times w$ 个,我们可以通过**循环**朴素地建边。

而第二种是**直接传输**,耗费 $n \times m$ 个,解决这个问题有很多种解法,这里我采用的是建立**原点**,将每个点都连接原点权值为 $n \times m$。为什么是正确的呢?我们来简单证明一下:若现在有两个点,这两点按照方案一要的字符数远大于方案二,而我们跑最小生成树的时候早就用 $n \times m$ 或更小的权值将这两个点直接或间接连一起了,所以这个方法是正确的。


建完了图,我们就可以在上面跑最小生成树了,我们在并查集的合并的时候可以**累加权值**,这样答案就出来了。

什么?你问方案怎么输出?我们可以合并并查集的时候建一个图,这个肯定是个树了,然后按照**前序遍历**输出即为步骤。
2023/12/23 10:12
加载中...