неориентированный граф источники питания и города путь

Question

У меня есть вопрос, касающийся этой проблемы:

Учитывая п города C1, C2, ..., Cn:

1. Стоимость построения электростанции в городе Ci является pi.
2. Построения неориентированных линий электропередач между городами Ci и Cj стоит w_ij.

Учитывая все затраты пи, w_ij, Desing алгоритм полиномиальное время, чтобы найти минимальный набор затрат на линии электропитания, которые соединяют Ci в другой город с электростанции.

У вас есть идеи, как я могу атаковать эту проблему?

Я думал что-то вроде динамического программирования, а также что-то вроде «если в городе Чи нет электростанции, тогда ему нужна связь с другим городом, поэтому мы можем найти для всех j, которые wi_j является самым маленьким », но я не совсем понимаю, как исходить из этого момента.

Может ли кто-нибудь мне помочь?

Спасибо!

Answer 1

Мы можем думать о строительстве электростанции в городе Ci в качестве выбора края веса pi, который соединяет Ci с узлом «Источник всей мощности».

Ваша проблема теперь сводится к поиску самого дешевого способа подключения всех узлов (1 узел для каждого города плюс 1 узел для нового «источника всей мощности»). Это стандартная проблема, известная как minimum spanning tree.