1.
Как решать задание ЕГЭ
Теория
Характеристика задания
1. Тип ответа: значение.
2. Структура содержания задания: дан текстовый файл с описанием ациклического ориентированного взвешенного графа. Указаны начальная и конечная вершины. Задание может быть сформулировано в одном из двух вариантов: найти кратчайший путь между начальной и конечной вершинами или определить количество различных путей, ведущих из начальной вершины в конечную.
3. Уровень сложности: повышенный.
4. Примерное время выполнения: \(12\) минут.
5. Количество баллов: \(1\).
6. Требуется специальное программное обеспечение: да.
7. Задание проверяет умение считывать и обрабатывать входные данные о графе из текстового файла, умение реализовывать алгоритм Дейкстры, грамотно применять структуры данных — словари, кучи.
Пример задания
В текстовом файле demo_23_full.txt содержится описание ациклического ориентированного
взвешенного графа. В каждой строке файла записаны два натуральных числа
(\(L\), \(M\)) и одно положительное вещественное число (\(W\)).
\(L\) и \(M\) — номера вершин графа, \(W\) — вес ребра, ведущего из вершины \(L\) в вершину \(M\). Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найди и запиши в ответе целую часть длины кратчайшего пути из вершины с номером \(1\) в вершину с номером \(100\). Существование хотя бы
одного такого пути гарантируется. Под длиной кратчайшего пути
понимается минимальная сумма весов рёбер, составляющих путь.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд.
\(L\) \(≤\) \(1000\),
\(M\) \(≤\) \(1000\);
\(W\) \(≤\) \(10 000\). Количество строк в файле не превосходит \(200\). Числа в строках
разделены произвольным ненулевым количеством пробелов и/или
табуляций.
Типовой пример организации данных во входном файле для графа на рисунке
\(100\) \(12\) \(1.0\)
\(6 \) \(7\) \(7.0\)
\(6\) \(1 \) \(1.0\)
\(1\) \(7 \) \(5.5\)
\(7\) \(100\) \(2.0\)
\(4\) \(100 \) \(8.0\)
\(1 \) \(100 \) \(12.0\)
\(1 \) \(4\) \(2.5\)
Для приведённого примера верным ответом будет \(7\).
План решения
- Установить тип задачи: определение кратчайшего пути или подсчёт количества путей.
- Прочитать файл и создать список смежности для графа.
- Инициализировать массив расстояний.
- Реализовать алгоритм Дейкстры для нахождения кратчайшего пути и алгоритм динамического программирования для подсчёта количества путей.
- Получить и оформить ответ.
- Проверить результат.
Этап \(1\). Установить тип задачи: приведённая в демоверсии задача на определение кратчайшего пути.
Этап \(2\). Прочитать файл и создать список смежности для графа.
Каждая строка разбивается на три значения: \( L\) — откуда, \(M\) — куда, \(W\) — вес. Граф сохраним в структуру словарь, где ключ — номер вершины, значение — список пар (куда, вес).
Этап \(3\). Создать список расстояний, заполнить его положительными бесконечностями, кроме начальной вершины, её величина — \(0\).
Этап \(4\). Выполнить алгоритм Дейкстры.
По шагам:
1) кладём стартовую вершину в очередь с приоритетом;
2) достаём вершину с минимальным расстоянием;
3) если расстояние в очереди устарело — пропускаем;
4) перебираем всех соседей, если находим путь короче — обновляем и кладём в очередь.
Этап \(5\). В условии необходимо вывести целую часть длины кратчайшего пути.
Этап \(6\). После получения ответа стоит проверить:
- ответ не меньше веса самого лёгкого ребра, выходящего из стартовой вершины;
- в ответ вписано целое число.
Программа
import heapq # модуль для работы с очередью с приоритетом
from collections import defaultdict # словарь, который сам создаёт пустой список
from collections import defaultdict # словарь, который сам создаёт пустой список
graph \(= \) defaultdict(list)
with open('demo_\(23\)_full).txt') as \(f\):
for line in \(f\):
parts \(=\) line.strip().split() # разбиваем входной файл по пробелам, убираем пробелы и переносы
\(L\), \(M \) \(=\) int(parts[\(0\)]), int(parts[\(1\)])
\(W \) \(= \) float(parts[\(2\)]) # учитываем, что вес — величина вещественная
graph[\(L\)].append((\(M\), \(W\)))
# готов словарь вершин
INF \(=\) float('inf')
dist \(=\) [INF] * \(1001 \) # список расстояний от вершины \(1 \) до всех остальных
dist[\(1\)] \(= 0.0 \) # расстояние от вершины \(1 \) до самой себя \(= \) \(0 \)
\(pq \) \(= \) [(\(0.0\), \(1\))] # очередь с приоритетом, стартовая вершина с расстоянием \(1 \)
with open('demo_\(23\)_full).txt') as \(f\):
for line in \(f\):
parts \(=\) line.strip().split() # разбиваем входной файл по пробелам, убираем пробелы и переносы
\(L\), \(M \) \(=\) int(parts[\(0\)]), int(parts[\(1\)])
\(W \) \(= \) float(parts[\(2\)]) # учитываем, что вес — величина вещественная
graph[\(L\)].append((\(M\), \(W\)))
# готов словарь вершин
INF \(=\) float('inf')
dist \(=\) [INF] * \(1001 \) # список расстояний от вершины \(1 \) до всех остальных
dist[\(1\)] \(= 0.0 \) # расстояние от вершины \(1 \) до самой себя \(= \) \(0 \)
\(pq \) \(= \) [(\(0.0\), \(1\))] # очередь с приоритетом, стартовая вершина с расстоянием \(1 \)
while \(pq\): # пока очередь не пуста, есть вершины, которые нужно обработать
\(d\), \(v \) \(=\) heapq.heappop(\(pq\)) # извлекаем пару с минимальным расстоянием \(d\) до вершины \(v\)
if \(d \) \(>\) dist[\(v\)]:
continue # расстояние \(d\) больше, чем сохранённое, пропускаем
for \(to\), \(w\) in graph[\(v\)]: # перебираем всех соседей вершины \(v\)
\(nd \) \(= \) \(d \) \(+~\)\(w \) # вычисляем новое расстояние \(= \) расстояние до \(v\) плюс вес ребра \(w\)
if \(nd \) \(<\) dist[\(to\)]: # если найденное расстояние меньше текущего, то нашли более короткий путь
dist[\(to\)] \(= \) \(nd \) # обновляем расстояние в списке
heapq.heappush(\(pq\), (\(nd\), \(to\))) # заносим расстояние в очередь
\(d\), \(v \) \(=\) heapq.heappop(\(pq\)) # извлекаем пару с минимальным расстоянием \(d\) до вершины \(v\)
if \(d \) \(>\) dist[\(v\)]:
continue # расстояние \(d\) больше, чем сохранённое, пропускаем
for \(to\), \(w\) in graph[\(v\)]: # перебираем всех соседей вершины \(v\)
\(nd \) \(= \) \(d \) \(+~\)\(w \) # вычисляем новое расстояние \(= \) расстояние до \(v\) плюс вес ребра \(w\)
if \(nd \) \(<\) dist[\(to\)]: # если найденное расстояние меньше текущего, то нашли более короткий путь
dist[\(to\)] \(= \) \(nd \) # обновляем расстояние в списке
heapq.heappush(\(pq\), (\(nd\), \(to\))) # заносим расстояние в очередь
print(int(dist[\(100\)])) # искали расстояние от \(1\)-й до \(100\)-й, здесь кратчайшее расстояние, берём его целую часть
Обрати внимание!
Суть алгоритма заключается в следующем: всегда берём ближайшую непосещённую вершину и пытаемся через неё улучшить пути ко всем её соседям. Так каждое расстояние становится оптимальным.
Для приведённого файла ответ \(10971\).
Пример задания на подсчёт количества путей
В текстовом файле demo_23_full_2.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (\(L\), \(M\)) — номера вершин ребра, ведущего из вершины \(L\) в вершину \(M\). Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найди и запиши в ответе количество путей, ведущих из вершины с номером \(1\) в вершину с номером \(100\). Существование хотя бы одного такого пути гарантируется.
Для выполнения этого задания следует написать программу. Вершины графа могут быть пронумерованы не подряд. \(L\) \(≤\) \(1000\), \(M\) \(≤\) \(1000\). Количество строк в файле не превосходит \(200\). Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.
Типовой пример организации данных во входном файле для графа на рисунке ниже.
\(100\) \(12\)
\(6 \) \(7\)
\(6\) \(1 \)
\(1\) \(7 \)
\(7\) \(100\)
\(4\) \(100 \)
\(1 \) \(100 \)
\(1 \) \(4\)
Для приведённого примера верным ответом будет \(3\).
План решения
- Установить тип задачи.
- Прочитать файл и создать список смежности для графа.
- Выполнить топологическую сортировку вершин (алгоритм поиска в глубину DFS).
- Реализовать алгоритм динамического программирования для подсчёта количества путей (ДП).
- Получить и оформить ответ.
- Проверить результат.
Этап \(1\). Установить тип задачи: приведённая задача на определение количества путей.
Этап \(2\). Прочитать файл и создать список смежности для графа. Каждая строка разбивается на два значения: \(L\) — откуда, \(M\) — куда. Разделитель — произвольное количество пробелов и/или табуляций, используем split(). Граф сохраняем в структуру словарь, ключ — номер вершины, значение — список вершин, куда ведут рёбра из неё. Параллельно собираем множество всех вершин, так как они могут быть пронумерованы не подряд.
Этап \(3\). Выполнить топологическую сортировку вершин. Топологическая сортировка расставляет вершины так, чтобы каждое ребро шло из более ранней вершины в более позднюю. Это нужно для того, чтобы при подсчёте путей каждая вершина обрабатывалась после всех своих предков.
- Находим непосещённую вершину, заходим в неё и отмечаем как посещённую.
- Рекурсивно обходим всех соседей, в которые ведут рёбра из текущей вершины.
- Когда все соседи обработаны, добавляем вершину в список посещённых.
- После завершения обхода переворачиваем список — получаем топологический порядок.
Этап \(4\). Динамическое программирование.
Заводим список dp[], где dp[\(v\)] — количество путей из вершины \(1\) в вершину \(v\).
1. dp[\(1\)] \(=\) \(1\) — в стартовую вершину ведёт один путь (пустой).
2. Обходим вершины в топологическом порядке.
3. Для каждой вершины \(v\), у которой dp[\(v\)] \(>\) \(0\), перебираем всех соседей \(u\).
4. Прибавляем dp[\(v\)] к dp[\(u\)] — каждый путь в \(v\) можно продолжить по ребру \(v\) — \(u\).
Этап \(5\). Оформление ответа.
Выводим целое число, соответствующее dp[\(100\)].
Этап \(6\). Проверка результата.
Ответ — положительное целое число не меньше \(1\). Если есть возможность — проверить вручную на небольшом графе.
Программа
from collections import defaultdict
# Чтение и построение графа
adj \(=\) defaultdict(list)
vertices \(=\) set()
with open("demo_\(23\)_full_\(2\).txt") as \(f\):
for line in \(f\):
parts \(=\) line.split()
if len(parts) \(>= \) \(2\):
\(u\), \(v \) \(=\) map(int, parts[:\(2\)])
adj[\(u\)].append(\(v\))
vertices.update((\(u\), \(v\)))
# Топологическая сортировка (DFS)
visited, order \(=\) set(), []
def dfs(\(v\)):
visited.add(\(v\))
for \(nb\) in adj[\(v\)]:
if \(nb\) not in visited:
dfs(\(nb\))
order.append(\(v\))
# Чтение и построение графа
adj \(=\) defaultdict(list)
vertices \(=\) set()
with open("demo_\(23\)_full_\(2\).txt") as \(f\):
for line in \(f\):
parts \(=\) line.split()
if len(parts) \(>= \) \(2\):
\(u\), \(v \) \(=\) map(int, parts[:\(2\)])
adj[\(u\)].append(\(v\))
vertices.update((\(u\), \(v\)))
# Топологическая сортировка (DFS)
visited, order \(=\) set(), []
def dfs(\(v\)):
visited.add(\(v\))
for \(nb\) in adj[\(v\)]:
if \(nb\) not in visited:
dfs(\(nb\))
order.append(\(v\))
for \(v\) in vertices:
if \(v\) not in visited:
dfs(\(v\))
order.reverse()
if \(v\) not in visited:
dfs(\(v\))
order.reverse()
# Подсчёт путей (ДП)
dp \(=\) defaultdict(int)
dp[\(1\)] \(= \) \(1\)
for \(v\) in order:
for \(nb\) in adj[\(v\)]:
dp[\(nb\)] \(+=\) dp[\(v\)]
dp \(=\) defaultdict(int)
dp[\(1\)] \(= \) \(1\)
for \(v\) in order:
for \(nb\) in adj[\(v\)]:
dp[\(nb\)] \(+=\) dp[\(v\)]
print(dp[\(100\)])
Обрати внимание!
Суть алгоритма заключается в следующем: упорядочиваем вершины по топологическому порядку, затем по очереди накапливаем количество путей от каждой вершины к её соседям. Так в финальной вершине накапливается общее число путей от стартовой вершины.
Для приведённого файла ответ будет \(203365335\).