1

私は最大の流れを独学していますが、この問題がありました:

元の問題は

  • ジョブのリストがあるとします

    {J1, J1,..., Jm}

  • そして、それらに応募した人々のリスト

    {P1, P2, P3,...,Pn}

  • 一人一人が異なる興味を持ち、中には複数の仕事に応募した人もいます(一人一人ができる仕事のリストを持っています)

  • 誰も3つ以上の仕事をすることは許されていません。

したがって、この問題は、下のグラフで最大フローを見つけることで解決できます。 ここに画像の説明を入力

この解決策は理解できましたが、

問題の難しいバージョン

これらの条件を追加するとどうなりますか?

  • 簡単なバージョンの最初の 3 つの条件 (仕事と人のリスト、および各人が興味または能力のリストを持っている) は同じです。

  • その会社は、Ji の仕事に Vi 人だけを雇用している

  • その会社はできるだけ多くの人を雇いたい

  • 人が行うことができる仕事の数に制限はありません。

私のソリューションがそれらの条件も満たすことができるようにするには、グラフにどのような違いを加える必要がありますか?または、別のアプローチが必要な場合は教えてください。

誰かが何かを言う前に、これは宿題ではありません。あくまで独学ですが、マキシマムフローを勉強していて、問題はそこにあったので、解決策はマキシマムフローを使うべきです。

4

1 に答える 1