Нам задан сетевой поток, а также максимальный поток в сети. Ребро будет называться возрастающим ребром, если увеличение его пропускной способности на произвольное положительное число также увеличит максимальный поток.
Представьте алгоритм, который находит возрастающее ребро (если оно существует) и работает за $O(n^2)$.
Я подумал о следующей идее -
- Найдите минимальный разрез в графе, полученный с помощью алгоритма Форда-Фулкерсона.
- Увеличьте пропускную способность всех ребер в левой части разреза на 1.
- Запустите BFS в остаточной сети, чтобы узнать, существует ли улучшенный путь. Если он существует, у нас есть возрастающее преимущество. Чтобы найти его, мы должны сравнить исходную сеть с новой сетью. Мы должны сделать это n раз, поскольку нам нужно проверять улучшенный путь каждый раз, когда мы увеличиваем емкость на 1.
Это правильно, и я в соответствии с требуемым временем работы?
Спасибо!
