ネットワーク・ストリーム・エントリー-最大ストリーム用Dinicアルゴリズム---Comzyhのブログから転載
4194 ワード
ネットワーク・フロー・エントリー-最大ストリームのDinicアルゴリズム
「ネットの流れは広くて奥深い」—sideman語
基本的なネットワークストリームの問題
WHDのご支援に感謝いたします
ネットワーク・ストリームの内容を最初に知ったのは最大ストリームの問題で、最大ストリームの問題はよく理解されています.
説明は必ず通俗しなければならない.
右図に示すように、パイプシステム、ノード{1,2,3,4}と、パイプ{A,B,C,D,E}と、図1枚がある.[1]は源点であり、無限の水量がある、[4]は合流点であり、配管容量は図に示す.試問[4]ポイント最大受信可能な水の流量は?
これは単純な最大流問題であり[4]点の最大流量は50であることは明らかである.
死理性派は注意してください:流量は単位時間内で、いつもできるでしょう!
しかし、複雑な図の最大ストリーム方法は何ですか.EK、Dinic、SAP、etcがあります.次にDinicアルゴリズムを紹介します(コードの直接点を見てください).
Dinicアルゴリズム
Dinicアルゴリズムの基本的な考え方:
残量ネットワークに基づいて階層図を計算します.
階層図においてDFSを用いて、拡張路が存在しないまで拡張する.
を拡大できないまで、上記の手順を繰り返します.
NOCOWから引いて、かなり簡単ですよね...
小贴士:
一般的にDinicアルゴリズムでは、ある側の残りの流量だけを記録する.
残量ネットワーク:逆アークを含む有向図、Dinicはループし、修正するたびに残量ネットワーク、階層図:階層図、[原点からある点までの最短距離]階層図で、距離が等しいものを1層とし、(例えば上図の階層は{1},{2,4},{3})DFS:それは言うまでもないでしょう...
拡大:既存の流量に基づいて新しい経路を発見し、発見した最大流量を拡大する(注意:増加量は必ずしもこの経路の流量ではなく、新しい流量と前回の流量の差である)増広路:既存の流量に基づいて発見された新しい経路.△早く仕事を探しに来なさい.前の仕事と何が違いますか.
余剰流量:一方の辺が広くなる(すなわち、それが拡大路の一部である、あるいは、拡大路がこの辺を通過する)と、この辺が通過する流量である.
逆円弧:Dinicアルゴリズムでは、1つの有向エッジについて、順方向(入力データ)エッジ残量がI減少すると、逆方向アーク残量がI 増加する別の逆エッジ(アーク)を確立する必要がある.
Comzyhの詳細な説明(プロセス):
Dinicアニメーションのデモ
BFSによる階層図の作成注意:階層図は現在の図に基づいて作成するので、階層図を繰り返し作成する.
DFS法を用いてソース点から合流点への経路を探索し,この経路の流量Iを得るこの経路に従って図全体を修正し,通過箇所の順方向エッジ流量をIに減少させ,逆方向エッジ流量をIに増加させ,Iが非負数であることに注意する.
DFSが新しいパスが見つからないまで手順2を繰り返し、手順1 を繰り返します.
注意(無視できます):
Dinic(実は他の多くの)アルゴリズムでは、拡張路を見つけた後、逆エッジをI 増加させる.
DinicにおけるDFSは階層図中のDFSのみであり、DFSの次のノードのDis(ソース点からの距離)が自分のDisより1大きいことを意味する.例えば、図1の最初のDFSでは、Dis[2]=1のため、1->2->4という経路は合法ではない.Dis[4]=1;
ステップ2において「この経路を得る流量I」の実装:DFS関数は、ソース点から現在最も狭い(残流量が最も小さい)エッジまでの残流量を表すパラメトリックlowを有し、DFSから合流点までの場合、Lowは我々が望む流量I である.
逆円弧(逆エッジ)の理解:
この段落は理解しなくてもいけないわけではありません.アルゴリズムを書くのに何の役にも立たないので、焦ったら、直接無視すればいいです.まず、右の図のような例を挙げます.
逆アークのフローネットワークを使用する必要があります
この図ではまず1−>2−>4−>5を広くするが、このとき容量2のストリームを得ることができるが、4−>2の逆アークを確立しなければ、さらに広くすることはできず、最終的な答えは2であり、明らかに間違っているが、逆アーク4−>2を確立すれば、2回目は1−>3−>4−>2−>5−>6の広がりを行うことができ、最大ストリームは3である.
Comzyhの逆アークの理解は「梁を盗んで柱を変える」と言えるので、よく読んでください.上記の例では、最終的な結果は1->2->5->6と1->2->4->6と1->3->4->6であることがわかります.1->2->4->5(符号A)を広くすると、1->3->4->2->5->6(符号B)を広くすることは、ノード2を通過するA流を中から切断する(合計2)2->5>6であり、2->4>6を歩かないことに相当するとともに、B流もノード4から1(合計1)を切断し、4->2->5->6ではなく4->6を歩くことに相当し、AB流に相当する加算を行う.
簡単に言えば、逆弧は今後後悔する機会を提供し、前にこの道を歩かないように別の道を歩かせる.
Dinicアルゴリズムのプログラム実装
最大ストリームアルゴリズムには、POJ 1273またはUCACO 4_という入門的な古典的な問題があります.2_1 NOCOW(中国語)から2つは同じ問題です
この問題のコードを与える
オリジナル文章、転載は明記してください(写真を持っていったほうがいい):Comzyhのブログから転載します
「ネットの流れは広くて奥深い」—sideman語
基本的なネットワークストリームの問題
WHDのご支援に感謝いたします
ネットワーク・ストリームの内容を最初に知ったのは最大ストリームの問題で、最大ストリームの問題はよく理解されています.
説明は必ず通俗しなければならない.
右図に示すように、パイプシステム、ノード{1,2,3,4}と、パイプ{A,B,C,D,E}と、図1枚がある.[1]は源点であり、無限の水量がある、[4]は合流点であり、配管容量は図に示す.試問[4]ポイント最大受信可能な水の流量は?
これは単純な最大流問題であり[4]点の最大流量は50であることは明らかである.
死理性派は注意してください:流量は単位時間内で、いつもできるでしょう!
しかし、複雑な図の最大ストリーム方法は何ですか.EK、Dinic、SAP、etcがあります.次にDinicアルゴリズムを紹介します(コードの直接点を見てください).
Dinicアルゴリズム
Dinicアルゴリズムの基本的な考え方:
残量ネットワークに基づいて階層図を計算します.
階層図においてDFSを用いて、拡張路が存在しないまで拡張する.
を拡大できないまで、上記の手順を繰り返します.
NOCOWから引いて、かなり簡単ですよね...
小贴士:
一般的にDinicアルゴリズムでは、ある側の残りの流量だけを記録する.
残量ネットワーク:逆アークを含む有向図、Dinicはループし、修正するたびに残量ネットワーク、階層図:階層図、[原点からある点までの最短距離]階層図で、距離が等しいものを1層とし、(例えば上図の階層は{1},{2,4},{3})DFS:それは言うまでもないでしょう...
拡大:既存の流量に基づいて新しい経路を発見し、発見した最大流量を拡大する(注意:増加量は必ずしもこの経路の流量ではなく、新しい流量と前回の流量の差である)増広路:既存の流量に基づいて発見された新しい経路.△早く仕事を探しに来なさい.前の仕事と何が違いますか.
余剰流量:一方の辺が広くなる(すなわち、それが拡大路の一部である、あるいは、拡大路がこの辺を通過する)と、この辺が通過する流量である.
逆円弧:Dinicアルゴリズムでは、1つの有向エッジについて、順方向(入力データ)エッジ残量がI減少すると、逆方向アーク残量がI 増加する別の逆エッジ(アーク)を確立する必要がある.
Comzyhの詳細な説明(プロセス):
Dinicアニメーションのデモ
BFSによる階層図の作成注意:階層図は現在の図に基づいて作成するので、階層図を繰り返し作成する.
DFS法を用いてソース点から合流点への経路を探索し,この経路の流量Iを得るこの経路に従って図全体を修正し,通過箇所の順方向エッジ流量をIに減少させ,逆方向エッジ流量をIに増加させ,Iが非負数であることに注意する.
DFSが新しいパスが見つからないまで手順2を繰り返し、手順1 を繰り返します.
注意(無視できます):
Dinic(実は他の多くの)アルゴリズムでは、拡張路を見つけた後、逆エッジをI 増加させる.
DinicにおけるDFSは階層図中のDFSのみであり、DFSの次のノードのDis(ソース点からの距離)が自分のDisより1大きいことを意味する.例えば、図1の最初のDFSでは、Dis[2]=1のため、1->2->4という経路は合法ではない.Dis[4]=1;
ステップ2において「この経路を得る流量I」の実装:DFS関数は、ソース点から現在最も狭い(残流量が最も小さい)エッジまでの残流量を表すパラメトリックlowを有し、DFSから合流点までの場合、Lowは我々が望む流量I である.
逆円弧(逆エッジ)の理解:
この段落は理解しなくてもいけないわけではありません.アルゴリズムを書くのに何の役にも立たないので、焦ったら、直接無視すればいいです.まず、右の図のような例を挙げます.
逆アークのフローネットワークを使用する必要があります
この図ではまず1−>2−>4−>5を広くするが、このとき容量2のストリームを得ることができるが、4−>2の逆アークを確立しなければ、さらに広くすることはできず、最終的な答えは2であり、明らかに間違っているが、逆アーク4−>2を確立すれば、2回目は1−>3−>4−>2−>5−>6の広がりを行うことができ、最大ストリームは3である.
Comzyhの逆アークの理解は「梁を盗んで柱を変える」と言えるので、よく読んでください.上記の例では、最終的な結果は1->2->5->6と1->2->4->6と1->3->4->6であることがわかります.1->2->4->5(符号A)を広くすると、1->3->4->2->5->6(符号B)を広くすることは、ノード2を通過するA流を中から切断する(合計2)2->5>6であり、2->4>6を歩かないことに相当するとともに、B流もノード4から1(合計1)を切断し、4->2->5->6ではなく4->6を歩くことに相当し、AB流に相当する加算を行う.
簡単に言えば、逆弧は今後後悔する機会を提供し、前にこの道を歩かないように別の道を歩かせる.
Dinicアルゴリズムのプログラム実装
最大ストリームアルゴリズムには、POJ 1273またはUCACO 4_という入門的な古典的な問題があります.2_1 NOCOW(中国語)から2つは同じ問題です
この問題のコードを与える
/*
Program:POJ 1273 /
Dinic
Author:Comzyh
*/
#include
#include
#include
#include
#define min(x,y) ((x0)
{
dis[i]=dis[j]+1;
q[++r]=i;
}
}
if (dis[N]>0)
return 1;
else
return 0;// DIS , BFS
}
//Find , , 0
int find(int x,int low)//Low ( )
{
int i,a=0;
if (x==N)return low;//
for (i=1;i<=N;i++)
if (tab[x][i] >0 //
&& dis[i]==dis[x]+1 //
&&(a=find(i,min(low,tab[x][i]))))// (a <> 0)
{
tab[x][i]-=a;
tab[i][x]+=a;
return a;
}
return 0;
}
int main()
{
//freopen("ditch.in" ,"r",stdin );
//freopen("ditch.out","w",stdout);
int i,j,f,t,flow,tans;
while (scanf("%d%d",&M,&N)!=EOF){
memset(tab,0,sizeof(tab));
for (i=1;i<=M;i++)
{
scanf("%d%d%d",&f,&t,&flow);
tab[f][t]+=flow;
}
//
ANS=0;
while (BFS())// , BFS
{
while(tans=find(1,0x7fffffff))ANS+=tans;// BFS ,
}
printf("%d
",ANS);
}
system("pause");
} オリジナル文章、転載は明記してください(写真を持っていったほうがいい):Comzyhのブログから転載します