Как реализовать Ford-Fulkerson в конкретной задаче?

Question

Я работаю над определенным упражнением и застрял.

Решить:

Решить проблему спроса на тираж. Есть некоторые заводы, которые производят товары, и некоторые деревни, куда товары должны быть доставлены. Они связаны сетью дорог, каждая из которых способна вместить максимальное количество товаров, которые могут пройти через нее. Проблема состоит в том, чтобы найти, существует ли обращение, которое удовлетворяет спрос. Эта проблема может быть преобразована в проблему максимального потока. Предположим, что каждый заводской узел fi имеет скорость производства pi. Кроме того, это di - уровень спроса в деревне VI. В качестве входных данных будет использоваться график, представленный с использованием списка смежности для каждого его узла. Сначала укажите число, описывающее количество узлов графа, а затем одну строку для списка смежности каждого узла (вместе с пропускной способностью), например. «D a 10 c 5» означает, что узел d подключен к a (с емкостью 10) и к c (с емкостью 5). Наконец, приведите показатели производства для каждого узла (там, где есть фабрики), а после этого снова укажите нормы спроса для деревень на каждом узле.

Как я понял, мне нужен такой файл ввода:

10
a b 10 c 20
b c 5 d 10
d e 7 f 8
a 10
e -5

//nodes = 10  
//directed graph -> a to b with capacity 10, a to c with capacity 20  
//a production = 10, e consumption = -5

Я пришел к выводу, что мне следует использовать алгоритм Форда-Фулкерсона, чтобы найти максимальный поток (поскольку это то, что запрашивается в качестве выходного сигнала)

Рассматривая различные реализации алгоритма (я рассматриваю возможность использования C или Java для его кодирования), я наткнулся на следующую проблему:

Ford-Fulkerson работает только с 1 источником и 1 раковиной. В этой задаче у нас есть тестовые случаи, когда есть 3 фабрики, например, и 2 деревни. Может ли кто-нибудь просветить меня, потому что я действительно застрял.

Answer 1

Это типичное расширение алгоритма Форда-Фулкерсона с одним источником и одним источником. По сути, вы рассматриваете другой «мнимый» узел U как источник 1 и подключаете этот узел U ко всем фабрикам. (т. е. какие K источники в вашей проблеме)

Аналогично, вы подключаете все M приемники, которые являются деревнями, к другому воображаемому узлу приемника V, который вы добавляете к данному графику. Затем, когда вы вычислите максимальный поток от U до V, вы вычислите максимальный поток от всех заводов до всех деревень.

Очевидно, что веса ребер, соединяющих U с фабриками, и тех, которые соединяют деревни с V, должны быть продуманы. В вашем случае каждый входящий фронт в фабрику с U должен иметь вес, равный емкости этого фабрики. В случае краев, соединяющих деревни с V, нет необходимости в ограничении, поэтому оно может быть таким же высоким, как максимальный вес во всем графе, или практическим значением, которое может представлять бесконечность.