基于 Capacity Scaling 的弱多项式复杂度最小费用流算法 | ouuan的博客

[utterances-bot]

基于 Capacity Scaling 的弱多项式复杂度最小费用流算法 | ouuan的博客

大多数人所使用的费用流算法 SSP（successive shortest path，即每次求出残量网络中 $s$ 到 $t$ 关于费用的最短路进行增广）是伪多项式的，最坏情况下复杂度为 $O(nmf)$，其中 $f$ 为最大流。已知有一种在点数为 $n$，边数为 $O(n^2)$，值域为 $O(2^{n/2})$ 时将其用时卡成 $O(2^{n/2}n^2\log n)$ 的构造方法。 本文将介

https://ouuan.github.io/%E5%9F%BA%E4%BA%8E-Capacity-Scaling-%E7%9A%84%E5%BC%B1%E5%A4%9A%E9%A1%B9%E5%BC%8F%E5%A4%8D%E6%9D%82%E5%BA%A6%E6%9C%80%E5%B0%8F%E8%B4%B9%E7%94%A8%E6%B5%81%E7%AE%97%E6%B3%95/

[zbw001]

C_p(u, v)+C_p(v, w)=p(u)+cost(u, v)+cost(v, w)+p(w) 是写错了吗？感觉应该是 C_p(u, v)+C_p(v, w)=p(u)+cost(u, v)+cost(v, w)-p(w)

[ouuan]

C_p(u, v)+C_p(v, w)=p(u)+cost(u, v)+cost(v, w)+p(w) 是写错了吗？感觉应该是 C_p(u, v)+C_p(v, w)=p(u)+cost(u, v)+cost(v, w)-p(w)

是写错了，感谢提醒。

[ouuan]

找到一篇非常好的文章，mark 一下：http://www.acta.sapientia.ro/acta-info/C4-1/info41-5.pdf

[Sweetlemon68]

SPFA 实现的该算法中，main 函数 110~114 行的下列代码是否是不需要的呢？

for (int i = 1; i <= n; ++i)
{
    add_edge(n + 1, i, 0, 0);
    cap[to.size() - 2] = 1;
}

这些代码疑似是防止溢出所用。注释掉这些代码后仍能 AC 模板。

[ouuan]

SPFA 实现的该算法中，main 函数 110~114 行的下列代码是否是不需要的呢？

for (int i = 1; i <= n; ++i)
{
    add_edge(n + 1, i, 0, 0);
    cap[to.size() - 2] = 1;
}

这些代码疑似是防止溢出所用。注释掉这些代码后仍能 AC 模板。

好像确实是不需要的，是防止溢出所用。感谢指出！