Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313251
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($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–7–100, 1–100 и 1–4–100$ не имеют общих рёбер, ответ $0$. Для пары вершин $6$ и $12$ обязательным является единственное ребро $100–12$, через которое проходят все четыре пути, ответ $1$.
Число путей $1 → 100$, проходящих через ребро $a → b$, равно (число путей $1 → a$) × (число путей $b → 100$) — только «вход» и «выход» — разные концы ребра. Ребро обязательно, если это произведение равно общему числу путей. Перебираем все $200$ рёбер; функция подсчёта с запоминанием делает это мгновенно.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список соседей
for line in open('23_20.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)
total = cnt(1, 100)
k = 0
for a in g:
for b in g[a]: # ребро a -> b
if cnt(1, a) * cnt(b, 100) == total: # все пути идут через него
k += 1
print(k)Второй способ — удалить ребро и убедиться, что путей не осталось (продолжение после чтения графа; для каждого ребра — своя функция со своим кэшем):
k = 0
for a in g:
for b in g[a]:
@lru_cache(None)
def f(v): # пути v -> 100 без ребра a -> b
if v == 100:
return 1
return sum(f(u) for u in g.get(v, []) if not (v == a and u == b))
if f(1) == 0: # без этого ребра путей не осталось
k += 1
print(k)Обязательные рёбра $932 → 666$ и $442 → 905$; через каждое проходят все $47 790 256$ путей. Обязательных вершин при этом четыре: $932, 666, 442, 905$.
20
