我对这个问题有疑问:
给定n个城市C1,C2,...,Cn:
- 在Ci城市 build 一座发电站的成本为pi。
- 在城市 Ci 和 Cj 之间 build 一条无向电力线的成本为 w_ij。
给定所有成本pi，w_ij，设计一个多项式时间算法来找到将Ci连接到另一个拥有电站的城市的供电路径的最小成本集。
您知道如何解决这个问题吗？
我一直在思考动态规划之类的事情，以及“如果城市 Ci 没有发电站，那么它需要与另一个城市的连接，所以我们可以找到所有 j 其中 wi_j 是最小的”，但我不太清楚如何从现在开始继续进行。
有人可以帮我吗？
谢谢!!
最佳答案
我们可以认为在 Ci 市 build 一个发电站是选择一条权重 pi 的边，将 Ci 与“所有电力之源”节点连接起来。
您的问题现在减少为寻找连接所有节点的最便宜的方式(每个城市 1 个节点，加上新的“所有力量之源”1 个节点)。这是一个标准问题，称为 minimum spanning tree .
关于algorithm - 无向图和城市电源路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34493928/