求教 dinic 费用流
  • 板块学术版
  • 楼主Winston12321_
  • 当前回复5
  • 已保存回复5
  • 发布时间2025/1/8 21:30
  • 上次更新2025/1/9 14:43:36
查看原帖
求教 dinic 费用流
396994
Winston12321_楼主2025/1/8 21:30

众所周知,大多数人的费用流都是用 EK+SPFA 实现的。

但是大家总说 dinic+SPFA 也可以,只需要把增广条件改为

dis[x]+cost(x,y)==dis[y]

即可。

在做某道题时,由于最段路长度的种类非常少,我想到了 dinic 费用流。然而我实现的代码会被某种图卡进死循环。

我没能在网上找到 dinic 费用流的正确写法,请问万能的谷友我可以在哪里找到呢?

2025/1/8 21:30
加载中...