Симбиоты внутри

Автор задачи и разработчик: Константин Бац

Представим схему передачи энергии в виде ориентированного графа. Назовем органы источниками, а симбиотов — потребителями. Источники и потребители будут вершинами, а связи — ребрами. Тогда задача заключается в том, чтобы построить граф, в котором существует путь от любого источника до любого потребителя, не проходящий через другие источники (чтобы каждый из потребителей продолжил бы получать энергию при их отказе). Среди всех таких графов требуется найти граф с минимальным количеством ребер, а среди всех таких — с минимальной суммарной длиной ребер.

В таком графе должно быть хотя бы $$$n + m - 1$$$ ребро. Действительно, при замене всех ориентированных ребер на неориентированные граф должен стать связным, а в связном графе не может быть меньше ребер. Заметим, что тогда в этом графе нет циклов, а значит если из $$$a$$$ достижима $$$b$$$, то из $$$b$$$ не достижима $$$a$$$. В таком случае все потребители должны быть достижимы из какого-то одного, с которым связаны все источники. Иначе для первого потребителя в топологической сортировке будет существовать источник, из которого он не достижим.

Поэтому минимальное число ребер достигается, когда все источники поставляют какому-то потребителю энергию, а он раздает ее другим. Схему передачи между потребителями тогда можно представить в виде подвешенного дерева. Суммарная длина связей в таком случае равна сумме евклидова расстояния от всех источников до некоторого потребителя и сумме всех ребер в дереве потребителей. Эти два слагаемых можно оптимизировать независимо, так как от выбора «первого» потребителя зависит лишь ориентация ребер в мин. остове.

Давайте минимизируем суммарную длину связей в дереве потребителей. Эту часть задачи можно решить алгоритмом поиска минимального остовного дерева в полном графе потребителей из $$$m$$$ вершин, для чего удобно воспользоваться алгоритмом Прима с асимптотикой $$$\mathcal{O}(m^2)$$$. Найти минимальную сумму расстояний от всех источников до некоторого потребителя можно, перебрав всех потребителей и для каждого посчитав расстояние до всех источников за $$$\mathcal{O}(nm)$$$.

Итого, строим минимальный остов за $$$\mathcal{O}(m^2)$$$, перебираем всех потребителей и выбираем среди них такой, от которого расстояние до всех источников будет минимальным за $$$\mathcal{O}(n m)$$$, и выводим ответ. Общее время работы — $$$\mathcal{O}(m \cdot (n + m))$$$.