最小コストの最大フロー

輸送の問題（古典的）は、倉庫から車両の消費地点に商品を輸送するための最適な計画の問題です。

古典的な輸送の問題では、2つのタイプのタスクが区別されます。コストの基準（輸送の最小コストを達成する）または距離と時間の基準（輸送に費やされる最小時間）です。

カットの下には多くのテキストがあります。 この問題を「写真で」解決するためのオプションの1つは、 グラフにあまり慣れていない人向けです。 添付リスト。


質問が出されたHabréと、基本的なアルゴリズムに関する記事が必要かどうかについて、記事が何らかの形でスリップしました。 リクエストに応答し、グラフ上のアルゴリズムとその実用化について少し話すことにしました。 どのレベルの知識に依存すべきかわからなかったので、比較的複雑で理論的に実用的なアルゴリズムを選択して、記事が少なくとも部分的に自然に適用されるようにしました。 同時に、グラフに特に精通していない人にも、非常に多くのことを伝えようとします。

問題（おとぎ話）：あなたは「グッズ」を生産している特定の工場の所有者であり、最近、別の都市にある1つの大企業と小売ネットワークへの商品の供給契約を結ぶことができました。 （ウラジオストクでは）非常に遠いので、商品は飛行機で配送する必要があります。 電話での会話中に、パートナーは次のように質問しました。 「。 あなたは考えていました...あなたは自分のトラック（トラック）を輸送しています。 空港は遠いです。 輸送の蓄積された統計を確認した後、輸送中に自分のエリアにいくつかの制限があることがわかりました。道路には貨物検査、重量管理のポイントがあり、一部の道路は完全に修復されています。 これをすべて1日あたりの道路の「 スループット 」と呼びます。 これらの条件に基づいて、1日あたり何箱の「グッズ」を空港に輸送できるかを調べる必要があります。 同時に、効果的にビジネスを行い、最短ルートで商品を配送したいのは、 タイヤの摩耗、メカニズム、および一般的な減価償却費です。

合計：ルートの合計距離を最小限に抑えながら、道路の容量を考慮して、1日に空港までいくつの箱を輸送できますか？

タスクはグラフ上で最も多くなります。 ソリューションは徐々に構築されます。
大きな問題はありません。小さな問題がたくさんあります。 （c）

私がそう言うかもしれない場合、アルゴリズムは、言う ネットにはたくさんの説明があります。

基本的な概念。 カウント？ 男爵？

この場合のロードマップは、グラフの形式で表示されます。 頂点は交差点であり、グラフの端は道路です。 bs骨（道路）には、距離（次の交差点まで）と1日のスループットの特性が割り当てられます。

コードでは、グラフは隣接リストまたは隣接行列の形式で表されます。 簡単にするために、隣接行列を使用します。 [u]と[v]の交点の隣接行列で頂点が「1」の場合、これらの頂点（交差点）はエッジ（道路）で接続されていることを意味します。 マトリックスに正確に「1」を指定する必要はありません。たとえば、距離やスループット（同様のマトリックス内）など、エッジに関連する他の有用な情報を保存することは非常に便利です。



この図は、主対角線に関して対称な行列を示しています。 M [u] [v] = M [v] [u] これは、 無向グラフが与えられ、任意の方向にエッジに沿って移動できることを意味します（往復）。 行列M [u] [v] = 1で、反対方向M [u] [v] = 0の場合、グラフは方向付けられ、頂点[u]から[v]までのみエッジに沿って進むことができます。

道路の道路容量は、行列C [..] [..]に書き込まれます。これは、一般的には有向グラフです。 結局のところ、「工場」から「空港」の方向に運転するには道路が必要です。 指定された帯域幅（プラントと空港）を持つ有向グラフは、 ネットワークと呼ばれます 。

グラフが特定の特性を計算する必要があるが、全体から大規模にではなく、ある頂点から他の頂点までの距離を想定する場合、配列を使用すると便利です（メモリが少なくなります）。 つまり 配列dist [..]の[u]セルに、「工場」から[u]上部までの距離を格納するとしましょう。 同様に、すでに訪れた頂点をマークする（ mark ）、持ってきたボックスの数を記録する（ push ）、頂点に来た場所を記録する（ pred ）ために、グラフを走査するときに配列を使用します。

わかった 素晴らしい。 マップをグラフに変換する方法を知っています。 そして、どうやって空港に箱を届けますか？ 「工場」から「空港」への道を見つけることができる必要があります。 このために使用します...

幅優先検索アルゴリズム、BFS。

ここまでは 、帯域幅と距離を考慮せずに、グラフの頂点の隣接関係（近傍） のみを考慮します 。

BFSは、他の多くの基盤となる最も基本的なアルゴリズムの1つです。
簡単な説明（写真は下にあります）。 現在、いくつかの開始（プラント）ピーク[s]に立っています。そこから、エッジに沿って隣接するピークのみが表示されます。 そして、できるだけ早くこのグラフのどこかにあるトップ[t]に到達する必要があります。 次にこれを行います。 私たちは、隣人の山の端（つまり、自由な道路）に沿って見ます。その中には[t]があります。 そうでない場合、「最初に検出された」すべてのネイバーを「そこに行く必要がある」キューに記録します。 すべての隣人を調べたとき-私たちはピークをマーク-「すでにここにいた」。 キューから最初の未訪問のピークを取得し、そこに行きます。

同じ方法で検索を続けます。 同時に、一度訪れたピークを無視します（後退ではありません）。 道路で[t]に出会ったら-すばらしい、目標は達成されました！

同じ交差点に数回入らないように、それらをmark [..]配列でマークします 。 [u]ピークの近傍を調べた後、 マーク[u] = 1を配置しました 。これは、 [u]番目の交差点を既に「訪問」していることを意味します。

写真：上部-シリアル番号が記載されています



アルゴリズムを完了すると、次の図が表示されます。



主な機能に注意してください。

• 各頂点は正確に（1回以下）取得します
• 頂点が最初に表示されるときに頂点をキューに入れます
• 植物から放射状に（波状に）グラフ内の他の頂点を見つけます
• 「検査半径」は常に増加しています
• 「空港」を見つけると、「工場」と「空港」の間のrib骨（道路）の数は最小限になります。 T.O. カウントの最速検査で「空港」を見つけます
• 私たちは、あなたが箱を運ぶことができる無料の道路だけを見ます！
• ええと…実際の距離（走行距離）を考慮するまで。

これで、「トバー」ボックスを空港に輸送する方法を見つける方法がわかりました。 さて...私たちはそれらを道路に沿って連れて行き、これを地図上にマークします。 このマーク-「いくつの箱、どの道路（端）、どの道を進むか」を「 フロー 」と呼びます。 マトリックス（ フロー ） F [..] [..]でこれに注意します 。 つまり [u]から[v ]までの途中で、 F [u] [v]箱を運びます。

現実に出会う時が来ました。マトリックス（ 容量 ） C [..] [..]で示される「帯域幅」を考慮する必要があります 。 実際、 [u]から[v]に向かう途中で、 C [u] [v]個の箱しか密輸できません。 それは残念です。

私たちは先見の明をもって行動しました。 BFSで「空港」を探している間、「訪問したピーク」をマークしている間、どの交差点から到着したかを記録しました。これをpred [..]配列に記録しました。 つまり 頂点pred [v]から頂点[v]に到達しました。 そしてちょうど前に、別の便利な配列を開始しました： push [v] 、つまり 道路[u]-[v]に沿って交差点[v]にボックスをどれだけ「プッシュ」できるか。
そして、彼らはそれを最新の状態に保ちました： push [v] = min（push [u]、C [u] [v] -F [u] [v]）;

このため、「空港」から「工場」までの軌道を逆の順序でもう一度「ほどいて」、このルートに沿っていくつの箱を運ぶことができるかを計算する必要があります。

Push [v] = push ["airport"] = flow = here！ 見つかったパスに沿って空港に配達された箱の数。 すべてのエッジ（道路）に沿ってルートを巻き戻し、パスのすべてのエッジに「フロー」 フローを追加します。

しかし、問題は物理的な量に関するものですが、箱の数、スループット、距離など、「 マイナス 」に直面する必要があるかもしれません...

フローを増やす（またはFord-Fulkersonアルゴリズム）

ここで、グラフの頂点の隣接（近傍）、エッジの方向帯域幅を考慮しますが、距離はまだ考慮していません。

（ボックスの）流れを上[u]から上[v]に増やすと、自然にF [u] [v] + = flowの操作を実行しますが、反対方向では、流れF [v] [u]-=フロー ; それが理由です。 この状況は可能です：

画像内：エッジ上-署名済み（ストリーム/帯域幅）



初めて、3つのボックスのストリームを最上部[i]に運び、エッジ[i]-[j ]を見つけました： minを転送しました（プッシュ[i]、C [i] [j]-F [i] [j]） = min（3、3-0）= 3ボックス、これをF [i] [j] + = 3とマークし、反対方向にF [j] [i]-= 3を設定します。

2回目は、最上部[j]で自分自身を見つけて、 min（push [j]、C [j] [i] -F [j] [i]）= min（6、0-（-3））= min（ 6、3 ）= 3から頂点[i]まで 。 ストリーム+3に対して-3ボックスをプッシュし、この道路に沿ったフローの補正を受け取りました。 しかし、次の反復の「空港」の方向に、残りの3つのボックスを追加で送信しました。

解釈：倉庫[j]から倉庫[i]に電話し、「3つの箱を自分用に残してください。別の用途を見つけて、代わりに3つ持ってきました。」 アルゴリズム自体が親切にそれらを見つけましたが。

ストリームの検索を続けます：

私たちは、成功している間、「空港」への道を探し続け、それらの上に箱を運ぶことに継続的に同意しました。 大まかに言うと、これは最大フロー検索アルゴリズム、またはFord-Fulkersonアルゴリズムと呼ばれます 。 また、BFSを使用して新しい配信ルートを「開く」ため、これはEdmonds-Karpアルゴリズムと呼ばれます。

箱を輸送して道路を完全に「飽和」させると、パートナーに「空港に1日何箱輸送できますか？」という質問に答えます。 しかし、それは彼ら自身の減価償却費について考える時です...タイヤ、ガソリン、摩耗...

BFSがグラフを検索するとき、距離について話している場合でも、逆流などの負の値を処理する必要があることはすでに明らかになっています（「金融用語」に結果があります）。 一般に、距離をさらに考慮する時間です...

距離 ジャック、道を進んでください！

このタスクを完全に完了する時が来ました：グラフの頂点の隣接（近傍）、エッジの指示されたスループット、距離。

「すべての方法で」引き出しで道路をロードするまで、BFSを実行し続けます。



では、何が起こったのか見てみましょう。 「空港」側から確認します。あるボックスが15 kmの距離を超えて到着した場合、つまり拒否した場合は15 km節約できます。 旅行（つまり、15を引く）が、別の移動方法を見つける（アタッチする）必要があります。

「空港」から前方（自由道路）と後方（押し戻して保存）のin骨に沿って歩いてみましょう。

画像：エッジ-符号付き（フロー/スループット）、および上-距離



上の図では、「負のサイクル」-6が見つかりましたが、まだ利用可能な（フリーまたは上流の）リブに沿って歩き続けています。 その中で1回転することで、それに参加する頂点の距離を-6減らすことができます。 これは、サイクルで輸送される箱の配送を節約できることを意味します。 箱を「ループに入れる」だけです。 上の写真では、6 km節約できます。 方法。

これで問題の解決方法がわかりましたが、これらのサイクルを検出するために...

ベルマンフォードアルゴリズム

頂点[s]から残りの頂点までの最短距離を見つけるために使用されます。 しかし、BFSとは異なり、短いパスはこのパスに沿ったグラフのエッジの数という意味ではなく、パスのエッジに沿った「距離」の合計という意味になります。

ただし、これには必要ありません。 これをダイクストラアルゴリズムと区別する主な機能の1つは、エッジの重みを負の数で指定できるグラフで機能することです。 アルゴリズムは、このようなグラフの副作用、つまり負の値のサイクルを検出できます。 必要なもの！

アルゴリズムはやや複雑です。 この実装は、Cormenの聖書とは関係ありませんが、うまく機能します。 見た目は、BFSに多少似ているため、説明を始めようと思います。

特定の頂点から開始し、「アクセス可能な」エッジに沿って隣接する頂点を見て、 dist [..]配列でそれらの距離を改善し、可能な限り小さくします。 このプロセスは「緩和」と呼ばれます。 そのような頂点を（エッジに沿って）「発見」した場合、頂点までの距離を更新し、それらの頂点を「それらからのグラフを改善してみてください」キューに入れます。 BFSに非常に似ています！ ただし、ピークをマークしません（「既に訪れた」）。同じピークに2回行かなければならない場合は、それを行います。

しかし、問題は、ピークまでの距離を縮め、永遠にスピンできる「負のサイクル」があるという事実に備えていますか？ プロセスは終了しません。 したがって、頂点の「検査半径」は、数N （頂点自体の数）によって制限されます。 これは、任意の頂点までの最小距離を計算するために十分に保証され、最も重要なことには、アルゴリズムはいずれの場合でも終了します。

これを行うには、最初の頂点をキューに入れ、その後に「スタブ」を置きます。これにより、キュー内の頂点が「検査半径0」にあることを示します。 キューから次のピークを取り出すと、突然「プラグ」を取得します。次の「検査半径」を示す新しいプラグを配置します。 ここに、一般に、アルゴリズムの全体のロジックがあります。 =）

ピークまでの距離の改善は、次の不等式によって検証されます。
dist [v]> dist [u] + edge_cost（u、v）

写真：エッジ上-長さ、およびツールチップ-現時点で見つかった最短距離



主な機能に注意してください（BFSとは異なります）。

• 頂上までの距離が改善されていれば、何度か頂上に着くことができます。 その後、このピークに入ってから、すでにピークからの距離を改善しようとします
• 距離が改善されたピークはキューに入れられます
• プラントから、距離に沿って（エッジに沿ってではなく）放射状に（波状に）残りのピークを見つけます
• 私たちは、箱を輸送する（または押し戻す）ことができる無料の道路のみを見ていきます。 したがって、与えられた距離とスループット

「半径N（頂点の数）」でグラフを表示すると、すべての頂点について最小距離が検出されます。 そして、これ以上減らすものはありません。 また、ピークの一部が「負のサイクル」に「引き込まれる」場合、平等違反をチェックすることで簡単に検出できます。 実際、サイクルでは、距離は無限に減少します。
dist [v]> dist [u] + edge_cost（u、v）

したがって、頂点[v]に対してこの不等式が成り立つ場合、負のサイクルに参加することを意味します。 必要なもの！ 私たちがそれに沿った道を彼女から「巻き戻し」、私たちは（彼女の）サイクルに沿って回転します。

すべて-サイクルが発見されました！ 残っているのは、ボックスの流れを「後方」に向けることです。これにより、ビジネスの効率が向上します。

最小コスト最大フローアルゴリズム：

• Edmonds-Carp Maximum Flowを見つけ始めます。
  • BFSは「工場」から「空港」への道を見つけます
    • 箱を運ぶ
• これまでのところ、Bellman-Fordアルゴリズムは「負のサイクル」を見つけます。
  • 「負のサイクル」の流れを元に戻します。
• 最小コスト（距離）の最大フローを取得しました

それだけです パートナーに電話して、1日に配達できる商品の数をお知らせします。 そして、節約したお金をどのように適用するかを考えます。 =）

int C[MAX_N][MAX_N]; // " "
int F[MAX_N][MAX_N]; // " "
int P[MAX_N][MAX_N]; // " ()"
int push[MAX_N]; // [v]
int mark[MAX_N]; // ,
int pred[MAX_N]; // [v] ()
int dist[MAX_N]; // [v]
int N, M, s ,t; // - , ,
int max_flow;
int min_cost;

void file_read()
{
int u, v, c, p;
in >> N >> M >> s >> t; N++;

for ( int i = 0; i < M; i++)
{
in >> u >> v >> c >> p;
C[u][v] = c;
P[u][v] = p;
P[v][u] = -p;
}
}

int edge_cost( int u, int v)
{
if ( C[u][v] - F[u][v] > 0 ) return P[u][v];
else return MAX_VAL;
}

int check_cycles()
{
for ( int u = 1; u < N; u++)
for ( int v = 1; v < N; v++)
if ( dist[v] > dist[u] + edge_cost(u, v) )
return u;

return MAX_VAL;
}

void init()
{
for ( int i = 1; i < N; i++)
{
mark[i] = 0;
push[i] = 0;
pred[i] = 0;
dist[i] = MAX_VAL;
}
}

//

int bf( int s)
{
init();
queue< int > Q;
pred[s] = s;
dist[s] = 0;

Q.push(s);
Q.push(MAX_N);

int u, series = 0;
while ( !Q.empty() )
{
while ( Q.front() == MAX_N )
{
Q.pop();
if ( ++series > N ) return check_cycles();
else Q.push(MAX_N);
}

u = Q.front(); Q.pop();
for ( int v = 1; v < N; v++)
if ( dist[v] > dist[u] + edge_cost(u, v) )
{
dist[v] = dist[u] + edge_cost(u, v);
pred[v] = u;
Q.push(v);
}
}
}

// -

int bfs( int s, int t)
{
init();
queue< int > Q;
mark[s] = 1;
pred[s] = s;
push[s] = MAX_VAL;

Q.push(s);
while ( !mark[t] && !Q.empty() )
{
int u = Q.front(); Q.pop();
for ( int v = 1; v < N; v++)
if ( !mark[v] && (C[u][v]-F[u][v] > 0) )
{
push[v] = min(push[u], C[u][v]-F[u][v]);
mark[v] = 1;
pred[v] = u;
Q.push(v);
}
}

return mark[t];
}

// -

void max_flow_ff()
{
int u, v, flow = 0;

while ( bfs(s, t) )
{
int add = push[t];

v = t; u = pred[v];
while ( v != s )
{
F[u][v] += add;
F[v][u] -= add;
v = u; u = pred[v];
}
flow += add;
}

max_flow = flow;
}

//

void min_cost_flow()
{
max_flow_ff();

int u, v, flow = 0;
int add = MAX_VAL;
int neg_cycle;

neg_cycle = bf(t);
while ( neg_cycle != MAX_VAL )
{
v = neg_cycle; u = pred[v];
do
{
add = min(add, C[u][v]-F[u][v]);
v = u; u = pred[v];
}
while ( v != neg_cycle );

v = neg_cycle; u = pred[v];
do
{
F[u][v] += add;
F[v][u] -= add;
v = u; u = pred[v];
}
while ( v != neg_cycle );

neg_cycle = bf(t);
}

for ( int u = 1; u < N; u++)
for ( int v = 1; v < N; v++)
if ( F[u][v] > 0 )
min_cost += F[u][v] * P[u][v];
}

void file_write()
{
out << max_flow << endl;
out << min_cost << endl;
}

void main()
{
file_read();
min_cost_flow();
file_write();
}

* This source code was highlighted with Source Code Highlighter .

//そして、このような条件を採用した場合：ピーク-道路の交差点、エッジ-道路、スループット-車線の数（許容速度など）からこれらの道路の現在の車の数を引いたもの。 「A」通りから「B」通りへの最大の流れを見つけます-市内で現在無料ではない道路は何ですか？ もちろん、もっと多くのパラメーターを考慮する必要がありますが、基本はグラフです。 これは面白いです。 =）

合計

あまりscられないでください

グラフについての投稿を始めたとき、私はどのレベルの能力に頼るべきかわかりませんでした。これまでのところ、たとえば、ダイクストラについては話さないことにしました。 突然、1秒ごとに暗記します。 しかし、Habr仲間がこれらのアルゴリズムの実用的な側面に興味を持っていたことは確かに覚えています。 したがって、彼は「球形」問題を取り上げ、その用語でグラフについて明確に伝えようとしました。

誰かがグラフとその応用例について興味を持ってくれることを願っています。 さらに、最も有名なプログラミングオリンピックACM ICPCの 1つについて、学生（学童）またはプログラミングを教える大学院生に思い出させるために記事を書くよう促されました！ 大学の初期にまだ決まっていない（あえてしなかった）人のために、チームを編成し、コンピュータクラスで遅くまで起き、アルゴリズムの漸近的挙動について議論し、それらの解決策と反例を考え出す。 アルゴリズムは興味深いものであり、一緒に集まる正当な理由であり、チームプレイの経験は貴重です。 今すぐ参加しよう！