From 761d8f2d49983a6db8663932f50085077324978b Mon Sep 17 00:00:00 2001 From: Shuhao Zhang Date: Sat, 9 Jan 2021 23:39:52 +0800 Subject: [PATCH] fix(min-cost): fix format --- docs/graph/flow/min-cost.md | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/docs/graph/flow/min-cost.md b/docs/graph/flow/min-cost.md index 898c4625..8c819260 100644 --- a/docs/graph/flow/min-cost.md +++ b/docs/graph/flow/min-cost.md @@ -173,7 +173,7 @@ Primal-Dual 原始对偶算法的思路与 [Johnson 全源最短路径算法](.. 容易发现,在一轮增广后,由于一些 $(i,j)$ 边在增广路上,残量网络上会相应多出一些 $(j,i)$ 边,且一定会满足 $d'_i+(w(i,j)+h_i-h_j)=d'_j$(否则 $(i,j)$ 边就不会在增广路上了)。稍作变形后可以得到 $w(j,i)+(h_j+d'_j)-(h_i+d'_i)=0$。因此新增的边的边权非负。 -而对于原有的边,在增广前,$d_'i+(w(i,j)+h_i-h_j) \geq 0$,因此 $w(i,j)+(d'_i+h_i)-(d'_j+h_j) \geq 0$,用 $h_i+d'_i$ 作为新势能并不会使 $(i,j)$ 的边权变为负。 +而对于原有的边,在增广前,$d'_i+(w(i,j)+h_i-h_j) \geq 0$,因此 $w(i,j)+(d'_i+h_i)-(d'_j+h_j) \geq 0$,用 $h_i+d'_i$ 作为新势能并不会使 $(i,j)$ 的边权变为负。 综上,增广后所有边的边权均非负,使用 Dijkstra 算法可以正确求出图上的最短路。 @@ -272,6 +272,7 @@ Primal-Dual 原始对偶算法的思路与 [Johnson 全源最短路径算法](.. printf("%d %d\n", maxf, minc); return 0; } + ``` ## 习题 -- 2.11.0