グラフの一部のエッジがフロー = 3n (n は非負の整数) でなければならないという最大フローの問題をどのように解決しますか? つまり、特定のエッジが 3 で割り切れるフローを持たなければならないという制約をどのように課すのでしょうか? たとえば、これらのエッジにはフロー 0、3、6、9... があるかもしれませんが、フロー 1、2、4、5 はないかもしれません... 理想的には、このようなグラフで最大フローを計算する方法が欲しいです。また、最大フロー構成の各エッジのフロー。
1 に答える
1
基本的に、最大フローを見つけるためのアルゴリズムを実装し、制約を組み込みます。
つまり、Ford-Fulkersonアルゴリズムを見てください。
アルゴリズムの 2.1 行目 (ウィキペディアで説明されているように) で、いくつかの
現在、この値はパス上の各エッジの最小値に基づいています。ここで、これらのエッジのいずれかに制約があるかどうかを確認し、それにc_f(p)応じて の値を変更します。
于 2015-10-16T05:16:47.807 に答える