蟻本はとりあえず急いでフローを求めたい人向けの説明なので、
アルゴリズムイントロダクション(図書館にある)とかを読むのをお勧めします。
http://hos.ac/slides/20150319_flow.pdf
これが分かりやすいですかね。
用語として、 フロー、フローの残余グラフ、増加路、カット、とかは理解しておきましょう。
増加路が存在しない⇔最大フローとか、 最大フロー最小カット定理、とかは理解しておくとよい。 #最大流について フローを増加路に従って愚直に増やしていくと、Ford-Fulkerson法ができる。O(FE)
また、最短路に沿って流すと残余グラフの最短路が広義単調増加していく、という知見から、 Edomonds-karp法ができる。O(VE^2)でフローの大きさに依らなくなる。
で、これをちょっと改善すると、残余グラフが狭義単調増加するO(V^2E)のDinic法になる。
ほかにも、MKM algorithm,wave algorithm,プッシュ再ラベル法,Link/Cut Treeを使ったDinic法 とかがあってもっと高速化できるらしいが日常ではDinic法で十分らしい。
また、フローを利用して、 二部グラフのマッチングや頂点被覆に利用することもできる。 (二部グラフの場合、最大マッチング=最小頂点被覆)
#アルゴリズムイントロダクションに載ってたJohnsonのアルゴリズム
有向グラフの全点対最短路をO(VElogV)で求められるのでグラフが疎な時に便利。
各頂点に適当に重みh(v)がついてるとき、辺の重みw(u,v)を、w'(u,v)=w(u,v)+h(u)-h(v)にしてやっても
最短路の重みは定数分しか変わらないので、
うまいことhを設定してやって全wを正にしてやることにより、
各頂点からの最短路を求めるのにDijkstra法を用いることができる。
で、hの求め方ですが、
新しく頂点sをもってきてやって、元のグラフの全頂点にsから長さ0の有向辺を張ってやった後、
各頂点vのsからの最短路をh(v)とする(これはBelmanford法で)。
まず、sありで負閉路があるなら、sを含む閉路はないので、元グラフに負閉路が存在する。
で、h(v)は各頂点からの最短キョリなので、h(u)+w(u,v)>=h(v)が成立し、
w'(u,v)=w(u,v)+h(u)-h(v)>=0が成り立つ。というわけでDijkstra法が使えてやったね!!という話。
計算量は、前処理O(EV)。本計算O(V)*O(ElogV)になるので全部でO(EV+VElogV)=O(VElogV)。
#最小費用流について
(蟻本のやつ、負費用閉路があるとちゃんとうごきませんよね....?)
最大流っぽく、最短経路に沿ってフローを流し続けてやればよい。
このときの計算量は、毎回O(VE)で最短路が求まるのでO(FVE)。
で、Johnsonのアルゴリズムと同様にうまいことポテンシャルを設定してやる、と、
各回O(ElogV)で最短路が求まるのでO(FElogV)で求まる、という話が蟻本の。
具体的には、始点sからの最短距離をポテンシャルh(v)にしてやればよい。
(これ、Johnsonのアルゴリズムも新しい頂点sを導入しなくてもいい、ってことになりますよね)
で、増加路にそってフローを流した後、頂点のポテンシャルh(v)を更新してやる必要がありますが、
これが直前のdistを足してくことによって求められるらしい、という話。(正直ちゃんとりかいしていない)
#参考文献 蟻本 アルゴリズムイントロダクション第二巻(図書館にある) http://hos.ac/slides/20150319_flow.pdf http://topcoder.g.hatena.ne.jp/Mi_Sawa/20140311