私は最大の流れを独学していますが、この問題がありました:
元の問題は
ジョブのリストがあるとします
{J1, J1,..., Jm}
そして、それらに応募した人々のリスト
{P1, P2, P3,...,Pn}
一人一人が異なる興味を持ち、中には複数の仕事に応募した人もいます(一人一人ができる仕事のリストを持っています)
誰も3つ以上の仕事をすることは許されていません。
したがって、この問題は、下のグラフで最大フローを見つけることで解決できます。
この解決策は理解できましたが、
問題の難しいバージョン
これらの条件を追加するとどうなりますか?
簡単なバージョンの最初の 3 つの条件 (仕事と人のリスト、および各人が興味または能力のリストを持っている) は同じです。
その会社は、Ji の仕事に Vi 人だけを雇用している
その会社はできるだけ多くの人を雇いたい
人が行うことができる仕事の数に制限はありません。
私のソリューションがそれらの条件も満たすことができるようにするには、グラフにどのような違いを加える必要がありますか?または、別のアプローチが必要な場合は教えてください。
誰かが何かを言う前に、これは宿題ではありません。あくまで独学ですが、マキシマムフローを勉強していて、問題はそこにあったので、解決策はマキシマムフローを使うべきです。