2

いくつかのエッジとノードを持つフローネットワークがあります。そのソースノードを離れるエッジに、最小フローを配置して、そのエッジに少なくともxフローが存在するようにします(それが不可能な場合は、それを知りたいと思います)。最大フローを見つけるためにFord-Fulkersonアルゴリズムを実装しましたが、これを行うためにアルゴリズムを調整する方法がわかりません。ソースノードを離れるエッジの容量を減らすことを考えましたが、それはうまくいきませんでした。

誰かがこの問題について正しい方向に私を導いてくれませんか?

前もって感謝します!

4

1 に答える 1

2

「エッジ要求のあるフロー」または「下限のあるフロー」を計算するためのアルゴリズムを探しています。これには多くの簡単なアルゴリズムがあります。 この一連のメモでは、考えられるアプローチの 1 つについて詳しく説明していますが、Google で簡単に検索すれば、これに関する詳細情報を見つけることができると思います。

お役に立てれば!

于 2013-01-05T19:05:10.587 に答える