Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313205
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($L, M$) и одно положительное вещественное число ($W$). $L, M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе количество различных путей из вершины с номером $1$ в вершину с номером $100$, длина которых не превосходит $93$. Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов рёбер, составляющих путь. Два пути считаются различными, если они отличаются хотя бы одним ребром.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. $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 |
Для приведённого примера при ограничении «не превосходит $11$» верным ответом будет $2$ (пути $1–7–100$ длиной $7,5$ и $1–4–100$ длиной $10,5$), а при ограничении «не превосходит $12$» — $3$.
У функции два параметра, но теперь второй — оставшийся «бюджет» длины: $f(v, rest)$ — число путей из $v$ в $100$ длиной не более rest. Переход: $f(v, rest) = Σ f(u, rest − w)$. Базы в строгом порядке: сначала «бюджет отрицателен — путей нет», затем «мы в $100$ — один путь». Если проверить $v == 100$ первой, путь, пришедший в $100$ с перерасходом, будет засчитан. Веса целые, поэтому различных значений rest не больше $X + 1$, и запоминание работает.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список (сосед, вес)
for line in open('23_17.txt'):
s = line.split() # любые пробелы и табуляции
if len(s) < 3: # пустая строка
continue
a, b, w = int(s[0]), int(s[1]), float(s[2])
g.setdefault(a, []).append((b, w))
X = 93
@lru_cache(None)
def f(v, rest): # число путей v -> 100 длиной <= rest
if rest < 0: # бюджет исчерпан — проверяем ПЕРВЫМ
return 0
if v == 100:
return 1
return sum(f(u, rest - w) for u, w in g.get(v, []))
print(f(1, X))Второй способ — функция «число путей длиной ровно rest» из задания $10$, просуммированная по всем длинам от $0$ до $X$:
@lru_cache(None)
def e(v, rest): # число путей v -> 100 длины rest
if v == 100:
return 1 if rest == 0 else 0
return sum(e(u, rest - w) for u, w in g.get(v, []) if rest - w >= 0)
print(sum(e(1, L) for L in range(X + 1))) # веса целые: длины 0, 1, ..., XИз них $14$ путей имеют длину ровно $93$ и $198$ — меньше $93$. Кратчайший путь имеет длину $42$, всего путей $1 → 100$ в файле $5 305 347$.
20
