求助一道生成树题目
  • 板块学术版
  • 楼主400iq
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/4/30 21:32
  • 上次更新2023/10/23 17:05:38
查看原帖
求助一道生成树题目
238173
400iq楼主2023/4/30 21:32

简述题意:

现有 nn 个村庄,村庄之间存在一些土路,它们共同构成一张无向联通图。

我们需要从中选出 mm 个村庄修建医院,为了方便就医,还需要将一些土路改造为公路。因此我们需要考虑修路成本和方便程度两个因素。

定义方便程度为:每个村庄到距离最近的有医院的村庄的距离之和。

定义修路成本为:将每个村庄到距离最近的有医院的村庄所经过的土路组成一个集合,修路成本为这些土路的长度之和。

需要设计一个方案,使得修路成本和方便程度的和最小。

2023/4/30 21:32
加载中...