Эффективное перепроектирование (НТО 25/26 :: ИЭС)

Условие

В рамках модернизации районной сети подстанции заменены на реклоузеры, способные направлять энергию по любому ребру в любом направлении. Компания «Никола Электроник» гарантирует 100%-ную* надёжность реклоузеров, они никогда не ломаются.

В вашем распоряжении связная сеть с главной подстанцией и реклоузерами. В ней слишком много лишних ЛЭП (линий электропередачи), которые невыгодно содержать. Нужно удалить как можно больше ЛЭП так, чтобы сеть оставалась связной, и чтобы все реклоузеры в среднем передавали мощность с главной подстанции как можно большему числу других реклоузеров в сети (это целевой показатель, а мы – за эффективность!).

Формат входных данных

В первой строке два целых числа через пробел, N (количество узлов) и M (количество ЛЭП).

Далее M строк, в каждой два целых числа – соединяемые узлы (нумерация с 0, ЛЭП неориентированная). Главная подстанция имеет номер 0.

Формат выходных данных

В первой строке одно целое число K – количество удалённых ЛЭП.

Во второй строке K целых чисел – номера удалённых ЛЭП.

Для решения этой задачи у вашей команды есть 20 попыток.

* Проверялось в солнечную безветренную погоду. Не является офертой.

Видео-разбор

Разбор

Целевым показателем каждого узла является количество узлов, получающих от него энергию. Нужно максимизировать среднее этого числа по всей сети.

Чем вытянутее сеть, тем выше данный показатель, так как в длинной цепочке первый узел обслуживает остальные узлы, второй на единицу меньше и так далее. Значит нужно строить именно вытянутую структуру.

Финальным решением является максимально глубокое связное дерево, построенное таким образом, что в первую очередь нам нужно попытаться простроить максимально глубокую ветвь, и лишь в конце присоединять к ней единичные узлы, желательно расположенные как можно удаленнее от начала. А все ребра, которые не вошли в данное дерево, необходимо удалить.