我主要是看这篇博客入门的网络流,至今仍有疑问。
主要是关于 dinic 的优化,在最大流部分,这篇博客的作者写到:
无用点优化不能替代当前弧优化,当前弧优化是 dinic 的核心(大致意思)
但是在用 spfa 求最小费用最大流的部分,他又说此时不能加当前弧优化,并给出了例子,是有一定道理的,于是他的代码中删去了无用点优化和当前弧优化。
然而我在实际做费用流题时发现,有的题不加优化会T,而加入当前弧优化或者无用点优化后就会好很多(并且单加其中一个时间都差不多),实际上他们的上限并没有变,所以这就变成了一个很玄学的问题,可能与数据的情况有关系,那多数的数据是什么样子的,在做费用流时到底应不应该加入当前弧优化呢?