Макс. Поток с ограничениями на краях

Question

Эй, поэтому у меня есть график, в котором 3 ребра входят в узел, и выходят 3 ребра, однако мне нужно только, чтобы исходящий фронт активировался, если бы имело место конкретное входящее ребро. Например, если мы имеем:

А -> N

B -> N

C -> N

N -> N '

N' -> А»

-N '-> B'

-N '-> С'

Мне нужен только поток через A ', если A имел поток и протекал через B, если B имел поток и т. Д.

В основном его ограничитель мощности по краям A, B, C и I не мог ограничить их вначале.

Как я могу добавить это ограничение к максимальному потоку и решить задачу максимального потока для заданного графика, предполагая, что этот сценарий происходит несколько раз?

Редактировать: я не могу также ограничить их емкость, потому что A ', B' и C 'используются позже на графике, поэтому я не могу переместить N и N' до конца и заставить объединенную емкость быть менее поздней на.

Answer 1

Если цель состоит в том, чтобы ограничить комбинированный поток, оставляя a, b и c до емкости n-> n ', просто переместите n узлов на другую сторону вашего графика. Другими словами, вы можете моделировать свою проблему, просто взяв поток из a, b и c и направляя его напрямую (или через их простые пары) в n, а затем из n напрямую (или снова через n ') в ваш приемник.

Редактировать: вы можете также поставить n перед a/b/c для того же эффекта.

Редактировать 2: Если вы говорите о реализации ford fulkerson, вы можете теоретически отфильтровать пути, которые вы не хотите указывать в путях расширения. Например, когда ваша программа идентифицирует возможный путь увеличения, не увеличивайте ее вдоль нее, если она оставляет поток a-> n не равным n '-> a' и т. Д.