无向图与城市电源路径

Question

关于这个问题，我有一个问题：

给定n个城市C1，C2，.，Cn

1. 在Ci市建造一座电站的费用是pi。
2. 在城市、Ci和Cj之间建造一条无方向的电力线路需要花费w_ij。

给定所有成本π，w_ij，设计一个多项式时间算法，以找到连接Ci到另一个有电站的城市的供电路径的最小成本集。

你知道我怎么解决这个问题吗？

我一直在想一些类似于动态规划的东西，还有类似于“如果Ci没有一个发电站，那么它需要连接到另一个城市，所以我们可以找到wi_j最小的j”，但我不太清楚如何从这一点出发。

有人能帮帮我吗？

谢谢！！

Answer 1

我们可以把在Ci市建设一个发电站看作是选择一个把Ci与“全功率源”节点连接起来的权π边。

您的问题现在减少到找到连接所有节点的最便宜的方法(每个城市有一个节点，新的“全电源源”有一个节点)。这是一个被称为最小生成树的标准问题。