問題タブ [max-flow]

古いシステムを使用して行われる仕事が n 件あります。それらを新しいシステムに変更すると、その仕事に対して双方向の利益が得られます。一部のジョブ ペア (i,j) には依存関係があります。ジョブを変更するが、その従属ペアを変更しない場合、xij のコストがかかります。ジョブ 1 は、新しいシステムでは実行できません。メリットを最大化するために、新しいシステムに変更するのに理想的な一連のジョブは何ですか (もちろんジョブ 1 を除く)。

これは私自身の言葉で言い換えたアルゴリズムの問​​題です。何らかの形の最大フローまたは循環に削減されるはずです。コストが新しいシステムに変更される他のジョブに依存しているという事実により、アプローチを思いつくのに非常に苦労しています（静的な値を最大フローグラフの設定に関連付けて、有効なソリューションを持っているようには見えません）。私はこれについてしばらく考えてきましたが、まだ適切なアプローチを見つけるのに苦労しています. この問題に対処する方法についての提案は大歓迎です!

複数のソースと特定の容量の複数のシンクを持つパイプのネットワークをシミュレートするアルゴリズムを考案しようとしています。

これまでのところ、古典的な Ford-Fulkerson アルゴリズムを使用してみましたが、次のグラフを考えると、私が遭遇する問題はこれです。

ソース容量が 1 のSと、シンク容量が 1 のB と Cの両方を考えると、フローは S - a - B となり、B は 1 に飽和し、C はフロー 0 のままになります。

B と Cの両方が 0.5 を受け取るように、ネットワーク全体にフローを均一に分散しようとしています。何か案は？

ありがとう！

メインにハードコーディングされたグラフから最大フローを取得するためのコードを作成しました。指示に従いましたが、このエラーが発生し続け、理由がわかりません。多くの部品を変更してデバッグしようとしましたが、わかりません。これはエラーです：

これが私のコードです：

これは、main の要約版です。

Ford Fulkerson アルゴリズムは O(|E|f) 時間で実行されます。ここで、f は最大フローです。ただし、O(|E|) を実行する方法はありますか?

O(|E|f) 未満で実行するための解決策の 1 つは、重み付き最短経路問題などを使用して経路を見つけることに関連するものを使用して、フローの最大の増加を可能にする拡張経路を選択することですが、 O(|E|) 時間で実行されることを保証しますか?

基本的に、拡張パスを見つけるために必要な時間の複雑さは無視します (つまり、アルゴリズムが何であれ、複雑さを O(1) とします)。

そのような方法がない場合、反例は何ですか? はいの場合、どのような方法を使用する必要がありますか?

問題: http://www.spoj.com/problems/DIVREL

問題は、与えられた要素の集合から、倍数でない (b 形式で割り切れる) 要素の最大数を見つけることだけです。要素からその倍数へのエッジを作成してグラフを作成すると、それは DAG になります。

ここで問題は、ディルワースの定理を使用してアンチチェーンのカーディナリティに等しいすべての頂点を含むチェーンの最小数を見つけることに変わります。これは部分的に順序付けられたセットであるためです。

最小チェーンは二部マッチングを使用して見つけることができます (方法: 最小パス カバーです) が、アンチチェーン要素自体を見つけることができませんか?

C++ で maxflow アルゴリズムを使用してフォアグラウンド/バックグラウンド セグメンテーションを行う必要があります。( http://wiki.icub.org/iCub/contrib/dox/html/poeticon_2src_2objSeg_2src_2maxflow-v3_802_2maxflow_8cpp_source.html )。RBGに従ってpngファイルからピクセルの配列を取得しますが、次のステップは何ですか。このアルゴリズムを問題に使用するにはどうすればよいですか?