maximale zweiteilige Übereinstimmung (Ford-Fulkerson)

Question

Ich las und http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm und habe Probleme zu verstehen. Es scheint, dass das Beispiel unter den Annahmen ist, dass jeder Job nur 1 Person annehmen kann und jede Person 1 Job will. Ich frage mich, wie sich der Algorithmus/Code ändern würde, wenn zum Beispiel das v-Set eine Kapazität von> 1 (kann mehrere Leute für diesen Job einstellen) und das U-Set> 1 (jede Person will mehr als 1 Job) hat?

Answer 1

Jobs zu ermöglichen, mehr als eine Person, die ihnen zugewiesen haben, dann würden Sie nur Kantenkapazitäten Jobs-Terminal (ähnlich wie Niklas B. beschrieben in his comment, aber nicht genau.)

Wie dies ändern :

die Kapazitäten von 1 vom Source zum People und 1 People-Jobs garantiert, dass eine Person immer nur für eine j ausgewählt werden ob (weil der maximale Fluss, den sie insgesamt beitragen können, 1 ist). Die Kapazitäten > 1 von Jobs bis Terminal ermöglichen jedoch, dass diesem Job mehr als eine Person zugewiesen werden kann.

Wenn eine Person auch mehr als 1 Job ausführen kann, dann den maximalen Durchfluss Source-Person erhöht dich um diesen Betrag:

Wo i, j, k und x sind Stand-In für Ganzzahlen mit Werten >= 1

Der Schlüssel, an den man sich hier erinnern muss, ist, dass die Flusskapazitäten links von People diktieren, wie viele Jobs sie möglicherweise haben nehmen, und die Durchflusskapazitäten rechts von Jobs diktieren, wie viele Personen dieser Job zugewiesen werden kann. Die Kapazitäten in der Mitte sollten sich nicht ändern.