Я работаю над конкретным упражнением, и я застрял.
Решать:
Решите проблему спроса на тираж. Есть несколько фабрик, которые производят товары, и несколько деревень, куда товары должны быть доставлены. Они связаны сетью дорог, каждая из которых имеет пропускную способность для максимального количества товаров, которые могут пройти по ней. Проблема состоит в том, чтобы найти, существует ли тираж, удовлетворяющий спрос. Эта задача может быть преобразована в задачу о максимальном потоке. Предположим, что каждый заводской узел 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 деревни. Может кто-нибудь просветить меня, потому что я действительно застрял.
