Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313196
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($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 |
Для приведённого примера для пары вершин $1$ и $100$ через вершины $7$ и $4$ проходит по одному пути, и условие единственности не выполнено. Для пары вершин $6$ и $12$ через вершину $100$ проходят все четыре пути, через вершину $1$ — три, через $7$ — два, через $4$ — один, поэтому ответом для этой пары была бы вершина $100$.
Число путей из $1$ в $100$ через вершину v равно произведению (число путей $1 → v$) × (число путей $v → 100$) — как в задании $5$. Достаточно посчитать это произведение для каждой вершины и выбрать наибольшее; функция подсчёта с запоминанием объявляется внутри cnt, поэтому для каждой пары (src, dst) кэш свой.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список соседей
for line in open('23_16.txt'):
s = line.split()
if len(s) < 3:
continue
a, b = int(s[0]), int(s[1]) # вес ребра не нужен
g.setdefault(a, []).append(b)
def cnt(src, dst): # число путей src -> dst
@lru_cache(None)
def f(v):
if v == dst:
return 1
return sum(f(u) for u in g.get(v, []))
return f(src)
verts = set(g) # все вершины графа
for v in g:
verts |= set(g[v])
best = max((cnt(1, v) * cnt(v, 100), v) for v in verts if v not in (1, 100))
print(best[1]) # номер вершиныВторой способ — через вычитание: путей через v столько же, сколько всего минус минуя v (продолжение после определения verts):
def cnt_ban(banned): # число путей 1 -> 100, минуя banned
@lru_cache(None)
def f(v):
if v == banned:
return 0
if v == 100:
return 1
return sum(f(u) for u in g.get(v, []))
return f(1)
total = cnt_ban(None)
best = max((total - cnt_ban(v), v) for v in verts if v not in (1, 100))
print(best[1])Через вершину $666$ проходит $458 091$ путь из $574 015$; на втором месте вершина $732$ ($355 564$ пути), на третьем — $29$ ($335 988$).
20
