Max Flow Edge Constraints

Question

Как решить проблему максимального потока, в которой некоторые ребра на графе должны иметь поток = 3n, где n - неотрицательное целое число? Другими словами, как вы накладываете ограничения на то, что определенные ребра должны иметь поток, делящийся на 3? Например, эти ребра могут иметь поток 0, 3, 6, 9 ... но могут не иметь потоков 1, 2, 4, 5 ... В идеале мне хотелось бы вычислить максимальный поток на графике, подобном этому, и также поток на каждом ребре в конфигурации максимального потока.

Answer 1

В принципе, реализуйте алгоритм поиска максимального потока и создайте в своем ограничении.

Что я имею в виду, посмотрите на алгоритм Ford-Fulkerson.
Обратите внимание, что в строке 2.1 алгоритма (как описано в Википедии) Вы нашли

Теперь это значение основано на минимуме каждого ребра на пути. Здесь вы проверяете, имеет ли какое-либо из этих границ какое-то ограничение, а затем измените значение c_f(p) соответственно.