Я читал http://www.geeksforgeeks.org/maximum-bipartite-matching/ и http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm, и у меня возникли проблемы с пониманием. Кажется, что пример основан на предположениях, что каждая работа может принимать только 1 человека, и каждый человек хочет 1 работу. Мне было интересно, как изменится алгоритм/код, если, например, набор v имеет емкость > 1 (можно нанять нескольких человек для этой работы), а u set > 1 (каждый человек хочет более 1 задания)?
Максимальное двудольное соответствие (ford-fulkerson)
Ответ 1
Чтобы задания могли иметь более одного человека, назначенного им, вы должны изменять только размер границ от Jobs до Terminal (подобно тому, как Niklas B. описал в его комментарий, но не совсем.)
Вот так:
Емкость 1 от Source до People и 1 от People до Jobs гарантирует, что человек будет выбран только для одного задания (поскольку максимальный поток, который они могут вносить в целом 1). Однако емкости > 1 от Jobs до Terminal позволяют назначить более одного человека для этой работы.
Если человек может выполнять более 1 задания, то максимальный поток от Source до Person увеличивается на эту величину:
Где i, j, k и x являются stand-ins для целых чисел со значениями >= 1
Ключевая вещь, которую следует помнить здесь, состоит в том, что пропускная способность слева от People диктует, сколько заданий они могут предпринять, а пропускные способности справа от Jobs определяют, сколько людей может быть назначено этой задаче. Емкости в середине не должны меняться.