Максимальный поток в сети
Графы
Экстремальная
Дана сеть: n вершин, список рёбер edges (каждое - [u, v, пропускная способность], возможны кратные рёбра между одной парой), источник source и сток sink.
Верните величину максимального потока из source в sink (алгоритм Эдмондса-Карпа: пока в остаточной сети есть путь из source в sink, ищите его через BFS и проводите по нему максимально возможный поток).
Сигнатура функции
max_flow(n: int, edges: list[list[int]], source: int, sink: int) -> int
Примеры
| Вход | Ожидаемый результат |
|---|
| [4, [[0, 1, 3], [0, 2, 2], [1, 2, 1], [1, 3, 2], [2, 3, 3]], 0, 3] | 5 |
| [2, [[0, 1, 5]], 0, 1] | 5 |
1решили
1пытались
100%успешность
Войдите, чтобы решить →