Теория графов

Решим простую задачу на графы, которая на первый взгляд такой не кажется. Сначала читаем развесистое условие и пытаемся понять, что требуется в задаче: Если переложить на язык алгоритмов, то надо покрыть граф путями. И есть специальные алгоритмы, которые справляются с этой задачей. Но они расчитаны на ориентированные графы. А в этой задаче по каждой дороге можно передвигаться в обоих направлениях. Если упростить задачу и сказать, что есть только один ковбой и спросить, можно ли заблокировать все дороги? Тогда мы получим вариант классической загадки про нарисовать фигуру, не отрывая руки...

Несложная задача про написание обхода в ширину, на которой можно потренировать и применить несколько трюков. Читаем условие: В этой задаче нужно построить кратчайший путь, поэтому это явно поиск в ширину или BFS. Этот алгоритм подробно разбирали при решении Задачи 127. Путь. Если вы с ним не знакомы, то рекомендую сначала прочитать тот разбор. По условию задачи, поле очень маленькое (помним, что алгоритм BFS работает за линейное время от количества вершин и рёбер в графе, то есть O(V + E)). Поэтому,...

Базовая задача без подводных камней на один из основных алгоритмов теории графов - поиск в ширину. Читаем условие: Поиск в ширину (волновой алгоритм, BFS) - один из способов обхода графа. Применяется для определения всех вершин, доступных из стартовой (например для нахождения компонент связности), и расстояния до них в невзвешенных графах. Часто алгоритм называют волновым, потому что схема его работы похожа на расширение кругов на воде: В алгоритмической реализации нет необходимости явно выделять...

Некоторое время назад в задаче были изменены тесты (и немного условие), поэтому решение из предыдущего разбора не проходит: Задача 707. Zuma. Давайте перерешивать: Если представить, что состояние на поле - это вершина графа, а выстрелы, которые ведут в другие состояния - это рёбра в графе, тогда получается, что надо найти кратчайший путь в графе из текущей вершины в вершину с пустым состоянием. Эта задача решается с помощью обхода в ширину (bfs). Но всевозможных состояний может быть очень много, поэтому надо попробовать их уменьшить (при этом не пропустив кратчайший путь)...

Задача, которая сделала правило Варнсдорфа широко известным. Но старожилы знают, что раньше формулировка задачи была другой. Давайте посмотрим, как она звучит сейчас: В первоначальной формулировке задачи на поле могли быть стенки, через которые конь мог перепрыгнуть, но на которые не мог вставать (отсюда осталось наследие во входных данных, из которых, по факту, нужна лишь позиция буквы "K"). Правило Варнсдорфа гласит, что при обходе доски коню надо следовать в то поле, из которого существует минимальное число ходов...

На сайте acmp.ru появились 300 новых задач, и сейчас самое время их решить. Это предпоследняя задача регионального этапа Всероссийской олимпиады школьников по информатике 2010 года, то есть уровень сложности выше среднего, но 48% кажутся сильно преувеличенными. Для тех, кто знаком с алгоритмами на графах, задача не представляет трудности и решается топологической сортировкой, которую проще всего реализовать с помощью поиска в глубину (dfs). Но давайте рассуждать так, как будто не знаем ничего про графы...