Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313082
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($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$ такой вершины нет (есть путь $1–100$ из одного ребра), а для пары вершин $6$ и $12$ такой вершиной является вершина $100$: все четыре пути из $6$ в $12$ ($6–7–100–12, 6–1–7–100–12, 6–1–100–12, 6–1–4–100–12$) проходят через неё.
Вершина $v$ обязательна тогда и только тогда, когда после её удаления путей из $1$ в $100$ не остаётся. Значит, достаточно для каждой вершины (кроме $1$ и $100$) посчитать число путей, минуя её, и напечатать те, для которых получился $0$. Заметьте, что множество вершин нужно собрать из обеих колонок файла: вершина, встречающаяся только как конец ребра, не является ключом словаря $g$.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список соседей
for line in open('23_9.txt'):
s = line.split()
if len(s) < 3:
continue
a, b = int(s[0]), int(s[1]) # вес ребра не нужен
g.setdefault(a, []).append(b)
def cnt(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)
verts = set(g) # все вершины графа
for v in g:
verts |= set(g[v])
for v in sorted(verts):
if v not in (1, 100) and cnt(v) == 0: # без v путей не осталось
print(v)Второй способ — через произведение: $v$ обязательна, если (число путей $1 → v$) × (число путей $v → 100$) равно общему числу путей $1 → 100$. Продолжение программы после определения cnt и verts:
total = cnt(None) # все пути 1 -> 100
def paths(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)
for v in sorted(verts):
if v not in (1, 100) and paths(1, v) * paths(v, 100) == total:
print(v)Все $10 083 038$ путей из $1$ в $100$ проходят через вершину $544$.
20
