如果不熟悉算法过程的话可以参考以下链接(中的代码)
- https://oi-wiki.org/graph/flow/min-cost/#primal-dual
- https://www.luogu.com.cn/blog/Mogician/Network-Flow-Guide
''引理'':若图\(G\)中有边\((u,v,w)\)(且均存在源点到\(u,v\)的最短路),则有
\[dis[v]\le dis[u]+w \]证明:由最短路定义易得。\(\blacksquare\)
''正确性'':要证正确性,即证每次跑Dijkstra之前,(没有负环——不过这是显然的——且)对所有边\((u,v,w)\)有新的边权
\[w' = h[u]-h[v]+w \ge 0 \tag{1}\label{ref1} \]证明:\(G\)增广后,每个点的势能\(Ep\)都加上了\(dis'\),变成了\(G\)中源点到每个点的最短路\(dis\)(见上面的第2个连接)。只需证明,在\(s\)到\(t\)的最短路上增加了一些负权反向边/删除了一些边后得到的\(G'\)中,对所有边\((u,v,w)\)都有\(\ref{ref1}\)成立
分两类讨论:
-
对所有不在最短路上的边\((u,v,w)\),因为\(w\)未变,故由引理,在图\(G\)上有\(dis[u]-dis[v]-w \ge 0\),成立。
-
对所有在最短路上的边\((u,v,w)\)有
\[dis[u] - dis[v] + w\ge 0 \\ dis[v] - dis[u] - (-w)\ge 0 \]即
\[dis[u] +w = dis[v] \]由于\((u,v,w)\)在最短路上,显然成立。\(\blacksquare\)
修改是必要的:因为\(G\)的最短路可能不为\(0\)(与\(prev(G)\)相比增加了,如图\(G=(V=\{1,2,3\},E=\{(1,2,1),(1,3,1),(2,3,1)\})\)在一次增广之后的情况),导致出现正权边,必须变为零边。(否则新图\(G'\)中会有负权,不能跑Dijkstra)