Spaghetti Source - 最大流 (Dinic)

目的 以下は Dinic の層別ネットワークによって最大流問題を解くアルゴリズムである． まず，始点から幅優先探索を行い，辺の本数の意味での最短路長 d を決定する．そして長さ d のフローを「流せる限り」流す．これを繰り返す． 「流せる限り」とは，そのフローを取り除くと増加パスがなくなることをいう．このようなフローのことをブロッキングフローというが，長さ d のブロッキングフローを流すと残余ネットワークの増加パスの長さが少なくとも 1 増加することが証明できる．そのため，高々 O(V) ステップでこのアルゴリズムは停止する．一回のステップは幅優先探索と O(V) 回の深さ優先探索で行えるので O(V E) である．したがって全体で O(V^2 E) で終了する． 計算量 O(V^2 E)． ソースコード #define RESIDUE(s,t) (capacity[s][t]-flow[