Death First Search — Episode 2

Условие

По легенде задачи, мы — хакеры, которые хотят запретить некому Bobnet’у общаться в своей внутренней сети. Сеть Bobnet разделена на несколько небольших сетей, в каждой подсети находится агент Bobnet, которому поручена передача информации путем перемещения от узла к узлу по каналам связи к шлюзам, ведущим в другие подсети.

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

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

Входные данные

Инициализирующий ввод

Строка 1: 3 целых числа $N, L, E$

  • $N$ — общее количество узлов на уровне, включая шлюзы.
  • $L$ — количество связей на уровне.
  • $E$ — количество выходных шлюзов на уровне.

Следующие $L$ строк: 2 целых числа в каждой строке $(N_1, N_2)$, указывающие на связь между узлами с индексами $N_1$ и $N_2$ в сети.

Следующие $E$ строк: 1 целое число $EI$, обозначающее индекс узла-шлюза.

Входные данные для одного игрового хода

1 целое число $SI$, представляющее собой индекс узла, на котором в этот ход находится агент Bobnet.

Ожидаемый выход для одного игрового хода

Одна строка, состоящая из двух целых чисел $C_1$ и $C_2$, разделенных пробелом. $C_1$ и $C_2$ — это индексы узлов, между которыми вы хотите разорвать связь.

Ограничения
$2 \leqslant N \leqslant 500$
$1 \leqslant L \leqslant 1000$
$1 \leqslant E \leqslant 20$
$0 \leqslant N_1, N_2 < N$
$0 \leqslant SI < N$
$0 \leqslant C_1, C_2 < N$
Время ожидания одного хода $\leqslant 150$мс.

Код

Решение

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

Для начала, нужно посчитать количество связей, ведущих ко шлюзам, для каждого узла и записать эти значения в массив values, хранящий для каждого узла ценность разрыва связи в нем. После этого мы запускаем поиск в ширину из узла, в котором находится агент Bobnet, дабы определить расстояния от него до узлов, связанных со шлюзами. Чем узел дальше — тем менее важно разрывать в нем связь прямо сейчас, поэтому из ценности каждого узла вычитаем расстояние до него. Однако, это еще не все, ведь на графе с картинки снизу этот алгоритм бы разорвал связь в узле с единицей, вместо двойки и проиграл, ведь агент может пойти по зеленому пути, каждый узел которого связан с каким-то шлюзом, а узел, помеченный двойкой — с двумя, поэтому алгоритм бы не успел порвать все связи к концу пути.

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

Остается только каждый ход выводить номер шлюза, значение values для которого максимальное.

Ссылки

One thought on “Death First Search — Episode 2

  1. — Добавьте метки (хештеги).
    — Попробуйте сделать так, чтобы объяснение было легче понять, чем сам код. Пока с кодом разобраться легче. Для начала, постарайтесь не использовать предложений из 53-х слов. Это, по мнению психологов, примерно на 33 слова больше чем в состоянии логически воспринять образованный человек.
    — Пожалуйста, уберите двоеточия в заголовках. Это не принято. Двоеточие обычно используется перед прямой речью или перечислением. И почти больше никогда.
    — Не нужно ставить пробелы перед знаками препинания. Иначе при переносе слов новая строка может начинаться с запятой или точки и это как-то странно выглядит.
    — Сделайте меньше либо равно как в ваших учебниках матаанализа.

Добавить комментарий