建议升蓝
查看原帖
建议升蓝
537934
litjohn楼主2024/12/17 18:34

本题的主流做法需要证明三个命题:

  1. kruskal 最小生成树的正确性
  2. 两点间最大边权最小的路径在最小生成树上
  3. 贪心地将每个 a 中元素匹配到最“近”的 b 中元素的正确性

仅是前两个问题就是货车运输,而且本题还有第三个命题的证明和使用并查集做贪心的部分,难度与货车运输接近,建议升蓝。

2024/12/17 18:34
加载中...