Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313316
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($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 |
Для приведённого примера длины трёх путей равны $7,5; 12,0$ и $10,5$, их сумма $30,0$, поэтому верным ответом будет $30$.
Функция возвращает пару (число путей, сумма их длин). Переход: если из $u$ в $100$ ведут $cu$ путей с суммарной длиной $su$, то, добавив спереди ребро $v → u$ веса $w$, мы получаем $cu$ путей из $v$ с суммарной длиной $su + w · cu$ — ребро входит в каждый из $cu$ путей. База: из $100$ один путь длины $0$. Пара считается за один проход.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список (сосед, вес)
for line in open('23_25.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 (1, 0)
c, s = 0, 0
for u, w in g.get(v, []):
cu, su = f(u)
c += cu
s += su + w * cu # ребро w входит в каждый из cu путей
return (c, s)
print(int(f(1)[1]))Второй способ — через вклад каждого ребра: ребро $a → b$ веса $w$ входит в $cnt(1, a) · cnt(b, 100)$ путей, поэтому сумма длин всех путей равна $Σ w · cnt(1, a) · cnt(b, 100)$ по всем рёбрам (продолжение после чтения графа):
def cnt(src, dst): # число путей src -> dst
@lru_cache(None)
def h(v):
if v == dst:
return 1
return sum(h(u) for u, w in g.get(v, []))
return h(src)
total = 0
for a in g:
for b, w in g[a]: # вклад ребра a -> b
total += w * cnt(1, a) * cnt(b, 100)
print(int(total))Всего путей $647 997$, средняя длина $304,24$; кратчайший путь имеет длину $74$, самый длинный — $530$.
20
