Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313421
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($L, M$) и одно положительное вещественное число ($W$). $L, M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Путь назовём восходящим, если веса рёбер вдоль него строго возрастают; путь из одного ребра считается восходящим. Найдите и запишите в ответе количество восходящих путей из вершины с номером $1$ в вершину с номером $100$. Существование хотя бы одного такого пути гарантируется. Два пути считаются различными, если они отличаются хотя бы одним ребром.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. $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 |
Для приведённого примера верным ответом будет $2$: путь $1–100$ состоит из одного ребра, на пути $1–4–100$ веса возрастают ($2,5 < 8,0$), а путь $1–7–100$ восходящим не является ($5,5 > 2,0$).
Состояние рекурсии — пара (вершина, вес последнего пройденного ребра): $f(v, last)$ — число восходящих путей из $v$ в $100$, у которых первое ребро тяжелее last. Переход перебирает только рёбра с весом больше last и передаёт их вес дальше. Начальное значение $last = 0$ (все веса положительны). Число состояний невелико: не больше числа рёбер.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список (сосед, вес)
for line in open('23_28.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))
@lru_cache(None)
def f(v, last): # восходящие v -> 100, ребро > last
if v == 100:
return 1
return sum(f(u, w) for u, w in g.get(v, []) if w > last)
print(f(1, 0)) # первое ребро — любоеВторой способ — динамика по рёбрам в порядке возрастания веса: для каждого ребра $a → b$ считаем число восходящих путей из $1$, заканчивающихся этим ребром, — единица, если $a = 1$, плюс сумма по более лёгким рёбрам, входящим в $a$ (продолжение после чтения графа):
edges = sorted((w, a, b) for a in g for b, w in g[a]) # по возрастанию веса
into = {} # вершина -> [(вес, число путей)]
for w, a, b in edges:
c = 1 if a == 1 else 0 # путь из одного ребра 1 -> b
for w2, c2 in into.get(a, []): # рёбра, входящие в a
if w2 < w: # предыдущее ребро легче
c += c2
into.setdefault(b, []).append((w, c)) # c путей 1 -> b
print(sum(c for w, c in into.get(100, [])))Нисходящих путей (веса строго убывают) в этом файле $4$, всего путей из $1$ в $100$ — $3 603 506$.
20
