Алгоритм Эдмондса Карпа и 0 1 возможностей
Какова верхняя граница Эдмондса Карпа (BFS), когда единственными доступными мощностями являются 0 и 1?
Я не понимаю разницы, когда емкости только 0 и 1, я знаю, что Ford Fulkerson находит, что значение потока равно 0 или 1, если емкости 0 и 1. Помогает ли это мне?
1 ответ
В алгоритме Эдмондса-Карпа в каждом прогоне одно из ребер будет насыщенным, поэтому нет разницы между 0 1 или случайными ребрами емкости. означает, что оба времени выполнения одинаковы, также алгоритм работает правильно.