построение графа

[Meteroka]

не совсем понимаю как решается задача:
Имеетсяn насесленных пунктов A_1,A_2,...,A_n где n=10. стоимость строительства дороги , соединяющей пункты A_iи A_jравна i+j, но из пункта A_1 можно построить лишь дороги в A_nи A_n_-_1,а из пункта A_2в A_n_-_1. Построить сеть дорог наименьшей стоимости, позволяющую попасть из любого пункта A_iв любой пункт A_j.
подскажите пажалста какие нибудь идеи по решению.....не совсем понимаю как решать.... получается что и из пункта A_1и A_2 можно построить дороги в один и тот же пункт?

[gris]

Получается, что нам придётся строить дорогу из $A_2$ в $A_9$ и больше $A_2$ не рассматривать. И $A_1$ присоединять к сети через $A_{10}$ или $A_9$. При этом с точки зрения стоимости выгоднее соединить $A_1$с обоими, а остальные пункты связать с этими через $A_9$ - $A_3$ за 12 уе.

Итак за 44 уе строим дороги $A_{10}$ - $A_1$ - $A_9$ -$A_2$ и $A_9$ - $A_3$, а потом сеть, соединяющую пункты с $A_3$ по $A_8$.
Вот здесь нет ограничений по строительству дорог и решение доовольно простое. Никакого динамического программирования.
Попробуйте нарисовать от руки.

[Meteroka]

спасибо вам ОГРОМНОЕ....теперь все понятно!=)

[PAV]

[mod="PAV"]Тема перемещена в карантин. Почему это произошло, можно понять, прочитав тему
Что такое карантин и что нужно делать, чтобы там оказаться
Там же описано, как исправлять ситуацию.[/mod]


Научитесь правильно оформлять формулы. В предлагаемой теме все описано, включая примеры ошибок, которые Вы упорно делаете. Отредактируйте свое сообщение.