Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313131
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($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–7–100 — 5,5$; $1–100 — 12,0$; $1–4–100 — 8,0$. Минимальная из этих величин равна $5,5$, поэтому верным ответом будет $5$.
Величина, которую мы минимизируем, — не сумма весов, а максимум весов на пути. Рекурсия та же, что для кратчайшего пути, но вместо $w + f(u)$ стоит $max(w, f(u))$: наибольшее ребро на пути «$v → u → … → 100$» — это большее из ребра $v → u$ и наибольшего ребра на продолжении. Приём общий: динамика по ациклическому графу работает для любой операции вдоль пути, которая не убывает при добавлении ребра (сумма, максимум, произведение положительных чисел).
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список (сосед, вес)
for line in open('23_12.txt'):
s = line.split() # любые пробелы и табуляции
if len(s) < 3: # пустая строка
continue
a, b, w = int(s[0]), int(s[1]), float(s[2])
g.setdefault(a, []).append((b, w))
@lru_cache(None)
def f(v): # min наибольшего ребра на пути
if v == 100:
return 0
best = float('inf')
for u, w in g.get(v, []):
best = min(best, max(w, f(u))) # вместо w + f(u) — max(w, f(u))
return best
print(int(f(1)))Второй способ — метод порога: ответ равен наименьшему весу $T$, при котором вершина $100$ достижима из $1$ по рёбрам веса не более $T$. Перебираем все различные веса по возрастанию и проверяем достижимость обходом (можно и двоичным поиском):
def reachable(T): # путь 1 -> 100 по рёбрам <= T
seen = {1}
stack = [1]
while stack:
v = stack.pop()
for u, w in g.get(v, []):
if w <= T and u not in seen:
seen.add(u)
stack.append(u)
return 100 in seen
weights = sorted(set(w for v in g for u, w in g[v]))
for T in weights: # первый порог, при котором путь есть
if reachable(T):
print(int(T))
breakНаибольшее ребро на оптимальном пути весит $2667,8$; путь $1 → 766 → 581 → 797 → 378 → 41 → 375 → 110 → 100$. Для сравнения: на кратчайшем по сумме пути (длина $9169,3$) наибольшее ребро весит $4130,7$.
20
