Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313503
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($L, M$) и одно положительное вещественное число ($W$). $L, M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе наибольшее количество различных путей между какой-либо парой вершин графа, то есть максимум по всем парам различных вершин ($A, B$) числа различных путей из вершины $A$ в вершину $B$. Два пути считаются различными, если они отличаются хотя бы одним ребром.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. $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 |
Для приведённого примера из вершины $6$ в вершину $12$ ведут четыре пути ($6–7–100–12, 6–1–7–100–12, 6–1–100–12, 6–1–4–100–12$), столько же — из $6$ в $100$; из $1$ в $100$ и из $1$ в $12$ — по три пути; для остальных пар путей меньше. Верным ответом будет $4$.
Для фиксированной конечной вершины $t$ одна функция с запоминанием даёт число путей из любой вершины в $t$, поэтому достаточно $50$ функций — по одной на каждую возможную цель — и перебора начальных вершин. Все вершины (включая те, что встречаются только как концы рёбер) должны участвовать в переборе и как начала, и как концы.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список соседей
for line in open('23_30.txt'):
s = line.split()
if len(s) < 3:
continue
a, b = int(s[0]), int(s[1]) # веса не нужны
g.setdefault(a, []).append(b)
verts = set(g) # все вершины графа
for v in g:
verts |= set(g[v])
best = 0
for t in verts: # для каждой конечной вершины t
@lru_cache(None)
def f(v): # число путей v -> t
if v == t:
return 1
return sum(f(u) for u in g.get(v, []))
for s in verts:
if s != t:
best = max(best, f(s))
print(best)Второй способ — симметричный: фиксируем начальную вершину $s$ и считаем число путей из $s$ в каждую вершину по обратному графу (продолжение после чтения графа и определения verts):
r = {} # обратный граф
for a in g:
for b in g[a]:
r.setdefault(b, []).append(a)
best = 0
for s in verts: # для каждой начальной вершины s
@lru_cache(None)
def h(v): # число путей s -> v
if v == s:
return 1
return sum(h(a) for a in r.get(v, []))
for t in verts:
if t != s:
best = max(best, h(t))
print(best)Максимум достигается для пары $845 → 626$. Для сравнения: из $1$ в $100$ ведут $19 993 000$ путей, наибольшее число путей из вершины $1$ — $286 909 311$, наибольшее число путей в вершину $100$ — $33 502 334$.
20
