本蒟蒻还没学。。。**同问**
by Siyuan @ 2018-05-08 22:39:46
@[Sooke](/space/show?uid=26673) Dijkstra比SPFA快，稳定很多
by Takanashi_Rikka @ 2018-05-08 22:45:21
@[Takanashi_Rikka](/space/show?uid=93507)
这里关键是 `Dinic` 和 `EK` 的比较
by Sooke @ 2018-05-08 22:54:54
可能是因为EK好写（雾）
by naive_wcx @ 2018-05-08 22:55:25
蜜汁Dinic+spfa..
EK是依靠SPFA来实现的，不存在什么Ek+SPFA的说法，SPFA就是EK的主函数，两者是包含而非并列的关系。
而Dinic跟spfa/dijkstra根本都没任何关系，它跑分层图多路增广。
Dinic跑mcmf应该说并不优秀。因为Dinic的核心思想是每次分层寻找可行流，多次增广，继续分层。如此记录每条流量的前后关系我个人感觉是比较麻烦的，意义不大。（甚至我怀疑每次dfs中，可能没法记录每条可行流的前后关系）
所以说mcmf不如直接写EK，又好理解又好写，两分钟一个板子，都不需要动脑子，多好。 @[Sooke](/space/show?uid=26673)
by SeKong @ 2018-05-08 23:35:34
费用流里 Dinic 无非是一次性增广所有最短路长度相同的流吧，在怀疑在边权离散的情况下这样的路径不多，应该没太大效果……
by Elegia @ 2018-05-09 07:50:48
emmm..大概我昨天脑抽了。。正常dinic应该是可以跑的，但我的dinic写法带了别的优化的，不能跑费用流的。。
by SeKong @ 2018-05-09 08:05:09
正常情况下不应该直接刚zkw吗？
by Marser @ 2018-05-09 09:45:24
Dinic的分层图本来就是最短路，
Dinic的主要优化是当前弧，但似乎求最小费用的时候，流过的边不一定满流（因为要保证费用最小嘛），所以不能用当前弧。
于是就是EK啦，正好需要spfa求一遍最短路，所以代码长得很像Dinic，但是还是个EK。
by 紫钦 @ 2018-06-19 13:54:50
楼主可能是想说prime dual？确实会快一些吧，这个在zkw的博客里提到过。
by Victorique @ 2018-06-20 08:36:53