差分约束
关于建边，大致有两种。
-
\(A_i \le A_j+B\)
这种是跑最短路，规定了 \(A_i\) 的上界，会使得求出的 \(A_i\) 最大。
-
\(A_i \ge A_j+B\)
这种是跑最长路，规定了 \(A_i\) 的下界，会使得求出的 \(A_i\) 最小。
要辨认题目要求的是最大值还是最小值，从而建不同的边，跑不同的 \(SPFA\)。
差分约束
发布时间 2023-11-09 18:38:00作者: tx344
关于建边，大致有两种。
\(A_i \le A_j+B\)
这种是跑最短路，规定了 \(A_i\) 的上界，会使得求出的 \(A_i\) 最大。
\(A_i \ge A_j+B\)
这种是跑最长路，规定了 \(A_i\) 的下界，会使得求出的 \(A_i\) 最小。
要辨认题目要求的是最大值还是最小值，从而建不同的边，跑不同的 \(SPFA\)。