SRM 457
Petr+ACRush部屋にあたっていきなり絶望した
250
めんどくさいので24*60*19通り全部生成して試した
235.46
500
あれーmodとらなかったらオーバーフローするんじゃね…
とか思ったら、全然そんなことはなかったｗ
どれがmod nで等しくなるかを全パターン試して、1〜nの振り分け方に+nするしないの自由度分を掛けた
315.58
1000
久しぶりのフローキター
と思ったが、超絶TLEしてorz
最小コスト求めるのはただの最小費用流で、そっから辞書順最小化するためには、経路修正すれば良い
辺e=(v,u)に流れている流量を減らすためには、残余グラフ上でv->uのパスを見つけてそっちに流せば良くて、このパスの費用が0ならもとのコストのままで切り替えれる
逆に、辺e=(v,u)に流したいときはu->vのパスを見つければ良い
残余グラフには負の辺がよゆーで含まれるけど、最小費用流計算時のポテンシャルを使えば負の辺なんてないので、コスト0の辺のみからなるパスを探せばおk
と思ったんだけど、なぜか通らない…
Petrのを見たらベルマンフォードしてたのでおとなしくベルマンフォードしたら余裕でTLEorz
よく見たらグラフのサイズがそもそも違ったｗ
で、サイズ修正したらコスト0辺でも通った…
バグってたのかたまたまなのかわからね
