Я думаю, что это похоже на версию задачи о максимальном потоке с неориентированным графом.
Таким образом, для каждого ребра a->b также верно b->a. его двунаправленность. И они имеют одинаковую емкость. Это означает, что если у меня есть пропускная способность 10 между двумя вершинами a, b и у меня есть поток из a в b стоимостью 5, то оставшаяся пропускная способность из a в b будет равна 5, а также оставшаяся пропускная способность из b в a.
Мое решение состоит в том, чтобы иметь одно направленное ребро от b к a и другое от a к b. Вопрос в том, если я уменьшу невязку от a->b в остаточном графе, я все еще увеличу невязку для обратного края b->a?