2
Ford-Fulkersonを使用してGの最大流量が計算され、Eに単位容量の新しいエッジが追加されたとします。最大流量の効率的な更新方法。 （tはそのOW flの値が更新されなければならないが、それ自体OW FL。Ford Fulkersonアルゴリズムで新しいエッジを追加した後、最大流量を効率的に計算しますか？
A
答えて
0
がG」が新しいエッジとグラフであるうEはGに添加した。我々は、能力を保持することに注意してください残りのエッジを流れる。
をすぐ増強経路をPにおけるG」を見つける。
Pが存在する場合、その経路に沿った流れを更新しますでG'に1を設定します。そうでなければ、フローは同じままです。
最終的なフロー値を示します。 pが存在する場合は、eを通過するため、これは正しいです。したがって、のpに沿ったフローの更新は、正確に1である。フォーク・フルカerson・アルゴリズムは、フローを整数ステップで増加させるので、この更新後には、増補パスはG 'にはない。
Pが存在しない場合mincutは0
関連する問題
- 1. Ford Fulkersonを使って効率的に最大流量を計算する
- 2. Ford Fulkersonを使用して二分グラフの最大流量を計算し、合計に達する値を決定する
- 3. NumPyで最小二乗アルゴリズムを効率的に計算する
- 4. Ford-Fulkersonアルゴリズムでバックエッジが必要なのはなぜですか？
- 5. 最小s-tカットからの最大流量の計算
- 6. treeviewブランチを追加する最も効率的なアルゴリズム
- 7. エッジでの制約が与えられた最大流量
- 8. 最大流量
- 9. Ford-Fulkersonを実装している関数のセグメンテーションフォルト
- 10. 大量のオーディオファイルをフォーマットする最も効率的な方法
- 11. Javaで大量のXMLファイルの先頭に属性を追加する最も効率的な方法は？
- 12. アルゴリズム：最大フローを使用して正しい行列値を計算する
- 13. オペレータの閉包を計算するための効率的な関数アルゴリズム
- 14. 大量のテキストで最も一般的なフレーズを見つける効率的なアルゴリズム
- 15. プロジェクトオイラー＃8：ブルートフォース計算よりも効率的なアルゴリズムはありますか？
- 16. 新しいコントロールを追加した後に新しい行を追加する
- 17. Java Executorは、キューの最後/最後に新しいタスクを追加します。
- 18. Rパーセンテージを計算して新しい列として追加する方法は？ （例の最後の2列）
- 19. ラジアルプロファイルを計算する最も効率的な方法
- 20. 2つの値の合計を計算するためにFreeBSD-11で新しいシステムコールを追加します。
- 21. 最大の空きスペースを決定するための効率的なアルゴリズム
- 22. 最大ペア数の計算アルゴリズム
- 23. 大量の変数を使用して大きなデータを効率的に最適化する方法
- 24. バッチファイル - 計算された日付をファイルの最後に追加
- 25. 大量のリストをHTMLで効率的に表示する
- 26. サイトマップを生成する最も効率的なアルゴリズムですか？
- 27. Mongoマッパーで大量のデータを効率的に取得できますか？
- 28. SQL/VBAで効率的に大量のフィールドを塗りつぶし
- 29. Openlayer2でポリゴンを追加して距離を計算したい
- 30. 最小面積計算アルゴリズム（エッジのみのタイル配置）
新しいエッジを使用増強経路を見つけることを試みるように、次いでmincut-maxflow引数で、これは最大流量です。これを行うには線形時間が必要です（1つのDFS） –
今まで書かれたコードを表示して、追加される新しいエッジを考慮せずに初期グラフの最大流量を計算できますか？ –
これまで理論的には明らかにしたいコードは書いていません。しかし、私はFord Fulkersonアルゴリズムを使用しています.... –