Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313022
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($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 |
Для приведенного примера верным ответом будет $12$.
В ациклическом графе самый длинный путь ищется той же рекурсией, что и кратчайший, с заменой $min$ на $max$. Принципиально важна база для тупиков: $−∞$, а не $0$, иначе путь, упирающийся в тупик, будет посчитан как «дошедший до $100$». Алгоритм Дейкстры для поиска самого длинного пути не подходит — его жадный выбор корректен только для минимума; вместо него можно использовать обход вершин в топологическом порядке.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список (сосед, вес)
for line in open('23_3.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): # самый длинный путь из v в 100
if v == 100:
return 0
best = float('-inf') # тупик: пути нет!
for u, w in g.get(v, []):
best = max(best, w + f(u))
return best
print(int(f(1)))Длина самого длинного пути $170717,7$; путь содержит $25$ рёбер: $1 → 214 → 932 → 841 → 222 → 435 → 530 → 306 → 361 → 108 → 3 → 969 → 60 → 851 → 137 → 449 → 535 → 235 → 880 → 161 → 471 → 279 → 527 → 594 → 294 → 478 → 100$.
20
