フロー押し戻し系

実装を何通りか試してみた,AOJ2313 ハコの魔女 にsubmitして確かめてます

a.隣接行列で持つ(int G)
N<=500なのでこの問題だとこれが一番良いと思う
b.vector Gを持つ
Nがもっとでかいとaの方法は無理.しかしこれにはまあわかりやすい欠陥があって,eraseが遅いです.(sortしててもダメで,なぜかというと消した奴の後ろのrevのrevがずれるから)
c.set Gを持つ
revでアクセス出来ないじゃん・・・ iteratorを持つと一応大丈夫(setのiteratorはeraseした奴以外ちゃんと保持される(らしい))だけど,辺の容量を変えるときとかに,setなので直接いじれなくて,一旦eraseしてinsertする(しかもそのときrevのrevを貼り直さなきゃいけない)みたいなクソみたいな処理が必要なのでやめるべき
d.map G[]を持つ
これはG[v] にuでアクセスするとその辺のcapが帰ってくる(辺に情報があるときは値の方に情報を入れとく,キーはto)ようなものにする.
こうするとrevはそもそも保持する必要がないし辺回すときの処理も楽だし割といいコトずくめな気がする

でまあdに決めたところで,Dinicのmapバージョンを作ったのだが,ちょっと遅い.
なぜかというと,dinicだと流す前に始点からbfsする必要があるので遅いんだと思う(押し戻し系だと始点はコロコロ変わる).
なのでFord_Fulkersonにした,こっちだとusedの初期化だけで済むので速い気がする.

ハコの魔女だと
a + FF 0.41sec([http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1074878#1])
d + Dinic 2.38sec([http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1418186#1])
d + FF 0.66sec([http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1418200#1])

で(aが速いのはあたりまえだけど)dinicのほうがかなり遅かった.
あとwafrelkaに聞いたら,「辺を消さなくてもcapを0にすればいいじゃん」と言われた,確かに・・・
しかもそっちのほうが速そうだよね.