Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313042
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($L, M$) и одно положительное вещественное число ($W$). $L, M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе количество различных путей из вершины с номером $1$ в вершину с номером $100$, проходящих через вершину с номером $455$ и не проходящих через вершину с номером $704$. Существование хотя бы одного такого пути гарантируется. Два пути считаются различными, если они отличаются хотя бы одним ребром.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000, M ≤ 1000; W ≤ 10 000$. Количество строк в файле не превосходит $200$. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.
Типовой пример организации данных во входном файле для графа на рисунке
| 100 6 6 1 7 4 1 1 | 12 7 1 7 100 100 100 4 | 1.0 7.0 1.0 5.5 2.0 8.0 12.0 2.5 |
Для приведённого примера при условии «через вершину $7$ и не через вершину $4$» верным ответом будет $1$ (путь $1–7–100$). Всего путей из $1$ в $100$ три, из них через вершину $7$ проходит один, не проходят через вершину $4$ два.
«Не проходящих через $M$» означает, что вершину $M$ можно просто вырезать из графа: возвращать $0$, как только рекурсия в неё попала (или не добавлять рёбра с $M$ при чтении файла). «Проходящих через $K$» — путь распадается на две части, и число путей равно произведению: (число путей $1 → K$ без $M$) × (число путей $K → 100$ без $M$). Веса рёбер не нужны.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {}
for line in open(’23_5.txt’):
s = line.split()
if len(s) < 3:
continue
a, b = int(s[0]), int(s[1]) # вес ребра не нужен
g.setdefault(a, []).append(b)
def cnt(src, dst, banned): # число путей src -> dst, минуя banned
@lru_cache(None)
def f(v):
if v == banned: # запрещённая вершина «вырезана»
return 0
if v == dst:
return 1
return sum(f(u) for u in g.get(v, []))
return f(src)
K, M = 455, 704
print(cnt(1, K, M) * cnt(K, 100, M))
Контроль: тот же результат даёт разность (число путей через $K$) − (число путей через $K$ и через $M$) = $2 092 845 − 1 523 340 = 569 505$; второй способ требует знать, какая из вершин $K$ и $M$ встречается на пути раньше, поэтому вырезание $M$ надёжнее.
20
