https://loj.ac/problem/127

这题就是数据很强的网络流模板题。。

导致正常的$dinic$及一些方法无法$ac$

目前有两个人用$push-relabel\ ac$，以及一个$dinic\ ac$（就是我）。

趁着没被再次$hack$发一发

首先有一个技巧，

$for(lim=2^k;lim;lim>>=1)$只跑$>=lim$的边

听说这样复杂度会优化成$O(nmlogC)$，我也不知道为什么

不过有的数据(包括随机数据)这样写会比原来还慢

而且后来被 @negiizhao $hack$了

我看到一个代码跑的很快但$wa$了极少的点

对拍后发现

Edge& forward = g[u][i], back = g[forward.dest][forward.back];

他没给反向边加流量!

我受到启发，先不加反向边跑一遍，然后一次性把反向边都加进去，然后再跑一遍。

事实证明这样效果很好。

因为大部分数据(包括随机数据)第一次就跑出了最优解，其余的也都跑出了较接近的解

（还顺便拿下了另一题的$rank1$）

$ac$代码：https://loj.ac/submission/69717

$upd$:原来那样被@oscar $hack$了,

于是我改进了一下，重复:不退流跑，一次性退流。

而且这样也比原来更简洁。

https://loj.ac/submission/71183

$upd:$已被@negiizhao卡成$O(n^{1.5}m)$