Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313385
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($L, M$) и одно положительное вещественное число ($W$). $L, M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе количество различных путей из вершины с номером $1$ в вершину с номером $100$, проходящих хотя бы через одну из вершин с номерами $364$ и $428$. Существование хотя бы одного такого пути гарантируется. Два пути считаются различными, если они отличаются хотя бы одним ребром.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. $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$ и $4$» верным ответом будет $2$: пути $1–7–100$ и $1–4–100$ (через вершину $7$ проходит один путь, через вершину $4$ — один, через обе сразу — ни одного).
Число путей через $K$ или через $M$ считается по формуле включений-исключений: (через $K$) + (через $M$) − (через обе). Каждое слагаемое — произведение счётчиков; для «через обе» порядок прохождения важен: путь идёт либо $1 → K → M → 100$, либо $1 → M → K → 100$, и в ациклическом графе не более одного из этих вариантов возможен (в этом файле путей из $364$ в $428$ пять, обратно — ноль).
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список соседей
for line in open('23_27.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)
K, M = 364, 428
thrK = cnt(1, K) * cnt(K, 100) # через K
thrM = cnt(1, M) * cnt(M, 100) # через M
both = (cnt(1, K) * cnt(K, M) * cnt(M, 100) # через K, потом M
+ cnt(1, M) * cnt(M, K) * cnt(K, 100)) # через M, потом K
print(thrK + thrM - both) # включения-исключенияВторой способ — через дополнение: «хотя бы через одну» = все пути минус пути, не проходящие ни через $K$, ни через $M$ (продолжение после определения $K$ и $M$):
def cnt_ban(banned): # число путей 1 -> 100, минуя banned
@lru_cache(None)
def f(v):
if v in banned:
return 0
if v == 100:
return 1
return sum(f(u) for u in g.get(v, []))
return f(1)
print(cnt_ban(()) - cnt_ban((K, M))) # все минус «ни через одну»Через вершину $364$ проходят $4 561 560$ путей, через $428$ — $5 802 797$, через обе — $3 294 460$; всего путей $8 600 519$, минуя обе вершины — $1 530 622$.
20
