MaxFlow

暇だったからいろんなMaxFlowを隣接行列でてきとーに実装してみた
あるごりずむのかいせつはちょーてきとーだから間違ってるかも

1)藤重さんのスケーリング使う版

1.辺の容量の最大値をaとする
2.始点から確実にa以上の流量が届く点を探索する
3.終点まで届いたら一気にa流す
4.届かなかったらaを半分にする
5.a>0の間2~4を繰り返す
O(n^3 log u_max)
30行くらい

2)藤重さんのスケーリング使わない版

1.始点から一番流量が届く点を探索する
2.終点まで届いたら一気に流す
3.終点に届かなくなるまで1~2を繰り返す
O(n^3 log u_max)
30行くらい

3)Dinic

1.始点から遠ざかる向きの辺だけからなるグラフを作る
2.そのグラフ上で流れなくなるまでフローを流す
3.全く流れなくなるまで1~2を繰り返す
O(n^4)
40行くらい

4)Goldberg-Tarjan

各頂点には流れてきた流量をためておけるタンクがあり、高さが定義されているとする
1.始点の高さをn、他の頂点の高さを0とし、始点から流せるだけ周りの点に流す
2.始点と終点以外で流量が余ってる点のうち一番高い所にある点から周りの低い点に流す
3.周りが全部高かったら自分の高さを(周りの一番低い点の高さ)+1にする
4.始点と終点以外に流量の余ってる点がなくなるまで2~3を繰り返す
O(n^3)
20行くらい

ランダムにグラフ作って実験してみたところ、2<3<1<<4な感じの実行時間で、藤重さんすげーと思ったけど、意図的に始点と終点離してみたらすごく遅くなってしまったのでやっぱDinicが一番だった
Tarjanはオーダー的には一番だけど、一番遅いうえになんか実行の度に実行時間が百倍くらい変化してカオスだった
なんかやけに短くなったし、もしかしたら間違ってるだけかも