众所周知,大多数人的费用流都是用 EK+SPFA 实现的。
但是大家总说 dinic+SPFA 也可以,只需要把增广条件改为
dis[x]+cost(x,y)==dis[y]
即可。
在做某道题时,由于最段路长度的种类非常少,我想到了 dinic 费用流。然而我实现的代码会被某种图卡进死循环。
我没能在网上找到 dinic 费用流的正确写法,请问万能的谷友我可以在哪里找到呢?