Задача 41: Агенты (Польская олимпиада по
информатике 2000)
Из-за участившихся раскрытий своих агентов, Комитет Государственной
Безопасности Бутыляндии решил провести реформу, направленную на
улучшение их деятельности. Первым делом необходимо обеспечить
безопасность встреч агентов. Ваша программа должна помочь в решении
этой проблемы. Вам дано описание путей в Бутыляндии и начальные
положения двух агентов. Ваша программа должна ответить, возможно ли
безопасная встреча этих агентов.
Чтобы быть в безопасности агенты должны соблюдать такие условия:
- Агенты двигаются в течение дня, и встречаются вечером,
- Агент должен изменять место пребывания каждый день,
- Агенты могут путешествовать только по дорогам, соединяющим города
(в Бутыляндии, имеются односторонние дороги),
- Агент не может двигаться слишком быстро (это может выглядеть очень
подозрительным) - в течение одного дня, он не может путешествовать
дальше, чем в соседний город,
- Расстояние между двумя связанными городами настолько коротко, что
агент, отправившись от одного города утром, достигнет другого
вечером,
- Встречей называется такое состояние, когда два агента находятся в
том же самом городе в тот же самый вечер.
Задача
Ваша программа должна
- Читать число городов и описания сети путей в Бутыляндии и
стартовые положения агентов из входного файла AGE.IN,
- Проверять, возможна ли безопасная встреча, и если так, то, через
сколько дней,
- Выводит результат в файл AGE.OUT.
Входные данные
В первой строке файла AGE.IN, имеются два целых числа n и m,
разделенные пробелом, где 1 <= n <= 250, 0 <= m <= n * (n-1).
Во второй строке даны два целых числа a1 и a2, разделенные пробелом,
1 <= a1, a2 <= n и a1 <> a2. a1 и a2 стартовые положения агентов
Номер 1 и Номер 2.
В m следующих строк даны пары чисел a и b, разделенные пробелом, 1
<= a, b <= n и a <> b. Эти числа означают, что имеется путь от
города a к городу b.
Выходные данные:
Единственная строка файла AGE.OUT должна содержать:
- Одно положительное целое число, которое является минимальным
временем (в днях) необходимым, чтобы устроить безопасную встречу
двух агентов, если она возможна,
- Слово NIE (НЕ в Польском) - если такая встреча не возможна.
Пример
AGE.IN:
6 7
1 5
1 2
4 5
2 3
3 4
4 1
5 4
5 6
AGE.OUT
3
Решение:
Во-первых, разберемся с входными данными. Естественно, что сеть
дорог в Бутыляндии (в польском оригинале она называлась Byteland)
представляет собой ориентированный граф, заданный списком ребер. Нам
будет удобнее пользоваться таблицей смежности (двумерным массивом,
который хранит в ячейке [x, y] 1 - если существует путь из x в y и 0
- в противном случае). Это делается на этапе чтения данных.
Заведем два одномерных булевских массива, с размером, равным
количеству городов. Первый будет указывать, в каких городах может
находиться первый агент, а второй - в каких может быть второй агент,
в определенный день. Переменную, которая указывает, какой сегодня
день, первоначально инициализируем нулем, а в массивах обозначим,
что агенты могут находиться исключительно в начальных городах.
Теперь переходим к следующему дню. Здесь надо использовать два
swap-массива, которые будут временно хранить информацию, в каких
городах мы окажемся сегодня вечером. Для того, чтобы получить этот
список городов, надо пройти по нашим булевским массивам и, если мы
нашли, что мы можем находиться в городе x в день n, то в день n + 1
мы можем находиться в любом из городов, в который мы можем добраться
из x. Занесем всю информацию об этих городах в swap-массивы, а затем
заменим наши массивы на swap (наступил день n + 1). Если хоть один
элемент и в первом и во втором массивах равен true (т.е. оба агента
оказались в одном и том же городе), то выводим номер дня.
Гораздо сложнее все обстоит с ответом NIE. Во-первых, его надо
давать в случае, если мы не можем оказаться ни в одном городе (т.е.
все пути завели нас в тупик). Но возможно, что такой ситуации не
будет, например, если агенты двигаются по кругу друг за другом.
Здесь надо придумать какое-то другое условие выхода с ответом NIE.
Самый простой вариант - поставить ограничение на количество дней, но
его сложно определить. Например, если существует два кольца длиной
113 и 127 и один общий город соединяет их, то может понадобиться
больше 14000 итераций для того, чтобы агенты встретились. Я не
придумал эффективного способа. Разве что, поставить ограничение на
количество итераций (n^2)/2. Работать это будет долго...
Единственный способ улучшить такой вариант - уменьшить константу
пропорциональности, т.е. выкинуть абсолютно все лишнее. Можно,
конечно, поступить по другому - поставить ограничение не (n^2)/2, а
n * 20, например, хотя есть шанс, что некоторые ответы будут не
правильные, но по времени все должно уложиться.
Далее
ð
