0

3 つのエッジがノードに入り、3 つのエッジが出てくるようなグラフがありますが、特定の入力エッジに容量がある場合にのみ、出力エッジをアクティブにする必要があります。たとえば、次の場合:

A -> N

B -> N

C -> N

N -> N'

N' -> A'

N' -> B'

N' -> C'

Aにフローがある場合はA'を通過するフローのみが必要であり、Bにフローがある場合はB'を通過するフローなどが必要です。

基本的に、エッジ A、B、C の容量リミッターであり、最初は容量を制限できませんでした。

この制約を最大フローに追加し、このシナリオが複数回発生すると仮定して、特定のグラフの最大フロー グラフの問題を解決するにはどうすればよいですか?

編集: A'、B'、および C' はグラフの後半で使用されるため、最終的にそれらの容量を制限することもできません。そのため、N と N' を最後に移動して、後で結合容量を強制的に小さくすることはできません。

4

1 に答える 1

1

目標が、a、b、c を残して結合されたフローを n->n' の容量に制限することである場合は、n ノードをグラフの反対側に移動するだけです。つまり、a、b、c からフローを取得し、それを直接 (またはそれらの素数ペアを介して) n に向け、次に n から直接 (または n' を介して) シンクに向けるだけで、問題をモデル化できます。

編集: 同じ効果のために、a/b/c の前に n を置くこともできます。

編集 2: ford fulkerson の実装について話している場合、理論的には、拡張パスのリストで不要なパスを除外できます。たとえば、プログラムが可能性のある拡張パスを特定する場合、フロー a->n が n'->a' などと等しくない場合は、それに沿って拡張しないでください。

于 2016-03-30T00:00:21.867 に答える