Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313343
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($L, M$) и одно положительное вещественное число ($W$). $L, M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе количество различных значений, которые принимает длина пути из вершины с номером $1$ в вершину с номером $100$ (по всем путям из вершины $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 |
Для приведённого примера пути имеют длины $7,5; 10,5 и 12,0$ — три различных значения, поэтому верным ответом будет $3$.
Значением функции становится не число, а множество: $f(v)$ — множество всех длин путей из $v$ в $100$. Переход: для каждого ребра $v → u$ ко всем длинам из $f(u)$ прибавляем $w$ и объединяем. Чтобы результат можно было кэшировать, возвращаем frozenset. Целые веса ограничивают число различных длин сотнями значений, поэтому множества маленькие.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список (сосед, вес)
for line in open('23_26.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 frozenset([0]) # один путь нулевой длины
s = set()
for u, w in g.get(v, []):
for L in f(u):
s.add(w + L)
return frozenset(s) # frozenset можно кэшировать
print(len(f(1)))Второй способ — функция «число путей длины ровно rest»: перебираем все длины от $0$ до длины самого длинного пути и считаем те, для которых путей больше нуля:
@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)
@lru_cache(None)
def longest(v): # самый длинный путь v -> 100
if v == 100:
return 0
return max([w + longest(u) for u, w in g.get(v, [])],
default=float('-inf'))
M = int(longest(1))
print(sum(1 for L in range(M + 1) if e(1, L) > 0))Длины путей лежат в диапазоне от $51$ до $571$ ($521$ целое значение), но $23$ значения не достигаются (например, $52$–$61$); число путей $508 915$, различных значений числа рёбер — $21$.
20
