去年的省选题.之前知道了是找负环.不过一直感觉好迷是个坑.最近又想了想发现也不是很麻烦.

当年省选的时候完全对比例题无感啊.经过一年之后终于觉悟了一点东西.

考虑一个网络流,每条边的流量上限是inf,只有从源出来的边不是.然后如果进行一次正向增广会使代价增加b+d,如果进行一次逆向增广的话代价会增加a-d,前提是有流量.于是只要二分一个答案,看下存不存在一个负环来增广就好了.

然后一个spfa就迷之拿了bzoj的rank1.好开心.