algorithm - 无向图和城市电源路径

Question

我有一个关于这个问题的问题:

给定 n 个城市 C1,C2,...,Cn:

1. 在 Ci 市 build 一座发电站的成本是 pi。
2. 在城市 Ci 和 Cj 之间 build 一条无向电力线需要 w_ij。

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

你知道我该如何解决这个问题吗？

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

谁能帮帮我？

谢谢!!

Answer 1

我们可以认为在城市 Ci build 一座发电站是选择一条权重为 pi 的边，该边将 Ci 与“所有能量之源”节点相连。

您的问题现在减少到找到连接所有节点的最便宜的方式(每个城市 1 个节点加上新的“所有力量之源”的 1 个节点)。这是一个标准问题，称为 minimum spanning tree .