有 $n$ 个变量 $x_1, x_2, \dots, x_n$ ，有 $c$ 个变量拥有初始值， $x_{p_1} = v_1, x_{p_2} = v_2, \dots, x_{p_c} = v_c$ ，其他变量值都为 $+\infty$ 。
有 $m$ 条更新，每一条用三个参数描述 $(u_i, v_i, w_i)$ ，操作是 $x_{u_1} \gets \min(x_{u_i}, x_{v_i} + w_i)$ 。每条更新都能被应用无限多次，且可以用任意顺序应用这些更新。
目标是找到一个有限或无限长的更新序列，使得顺序应用这些更新后，除一些不可能被更新过或不存在最小值的变量外，每个变量都被充分更新。即不存在另一个更新序列能使最小值取到更小或最小值从存在取到不存在。
求出每个变量被充分更新后的值，或报告一些变量不可能被更新过或不存在最小值。

我给上面的问题随便编了个名字，叫做 <min, +> 变量更新问题。

<min, +> 变量更新问题一般有两种解决方法，分别是原 dag 上 dp 和原图上最短路。

这里的原图，指的是将每个变量看成一个点，每次更新视作

u_i

连向

v_i

边权为

w_i

的一条有向边后构成的图。原 dag 指的是要求原图为 dag 的情况下。

原 dag 上 dp

O(n + m)

解决。

具体的：

使用拓扑排序求出拓扑序，此时顺序遍历拓扑序的所有点，遍历到一个点时，顺序将它的所有出边加入更新序列。流程结束后的更新序列就是一个可以使得每个变量被充分更新的更新序列。

原图上最短路

$c$ 的取值

若

c = 1

，大家叫它单源最短路，若

c > 1

，大家叫它多源最短路。在其他条件相同的情况下，一般情况下，

c

的取值不会影响时间复杂度，因此下面不做分类。

若 $w_i \ge 0$

若无特殊限制

O((n + m) \log n)

解决。

使用 dijkstra。

若 $w_i$ 取值只有 $O(1)$ 个时：

O(n + m)

解决。

若

w_i

取值只有一种时，大家叫它 bfs。

若

w_i = 0/1

时，大家叫它 01bfs。

其他情况没有个公认的名字，使用

O(1)

个普通队列代替优先队列即可。

若 $w_i$ 无特殊限制

O(nm)

解决。

使用 Bellman-Ford 或 Bellman-Ford 队列优化（SPFA）。

总结

在原图上最短路是最通用的 <min, +> 变量更新问题的解决方法，是原 dag 上 dp 适用范围的超集。

<min, +> 变量更新问题

文章操作

原 dag 上 dp

原图上最短路

$c$ 的取值

若 $w_i \ge 0$

若无特殊限制

若 $w_i$ 取值只有 $O(1)$ 个时：

若 $w_i$ 无特殊限制

总结

相关推荐

评论

<min, +> 变量更新问题

文章操作

原 dag 上 dp

原图上最短路

ccc 的取值

若 wi≥0w_i \ge 0wi​≥0

若无特殊限制

若 wiw_iwi​ 取值只有 O(1)O(1)O(1) 个时：

若 wiw_iwi​ 无特殊限制

总结

相关推荐

评论

$c$ 的取值

若 $w_i \ge 0$

若 $w_i$ 取值只有 $O(1)$ 个时：

若 $w_i$ 无特殊限制