Михаил Густокашин против бюрократии(#1063) Игра в слова(#1065)
#1064

Задача g6_1064: Агенты (Польская олимпиада по информатике 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
Решение g6_1064:
Во-первых, разберемся с входными данными. Естественно, что сеть дорог в Бутыляндии (в польском оригинале она называлась 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, например, хотя есть шанс, что некоторые ответы будут не правильные, но по времени все должно уложиться.
Скачать тесты к задаче

Наверх