[正经分析] DAG上dp两种做法的区别——拓扑序与SPFA

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

在下最近刷了几道DAG图上dp的题目。
要提到的第一道是NOIP原题《最优贸易》。这是一个缩点后带点权的DAG上dp，它同时规定了起点和终点。
第二道是洛谷上的NOI导刊题目《最长路》，一个裸的DAG上dp，也同时规定了起点和终点。
对于这两道题目，我分别用了两种不同的方法来写。
第一道题目，我建立了一个反向图，从起点和终点分别用两张图来进行Floodfill，若某个点不能被两遍Floodfill遍历到，则这个点是无用点，应当剔除。这样是为了方便后面作DAG上dp时，使用拓扑序来进行过程。
第二道题目，我直接用了spfa，把松弛的条件的小于号改成大于号。
而后我才发现，第一题也可以用spfa写。

这是为什么？

我想了一下。首先spfa跑最长路，它得保证是一张DAG。否则你可以在一个正权环上无限的松弛下去。
其次考虑一下最长路的DAG拓扑序dp做法。
是不是一个点，能够更新它的状态的点的状态全部被确定了，它的状态才能够被确定？
然而SPFA并不是这么做的。因为类似BFS过程的缘故，可能一条路径已经早就更新了这个点的状态，而另一条能松弛它的路径还没能更新它的点状态。
这样子得到的结果会是错误的吗？并不会。 SPFA有效的避免了错解情况的发生。

讨论以下情况：
a->b 路径A：中间有几个点路径B：中间有十几个点。
b->c 只有一条路径。
a的入度为0。

DAG-dp情况：
首先从a开始拓扑序dp。显然a->b 路径上的所有点的状态确定下来后，b的状态被确定，随后b->c的状态一个个地被确定。

SPFA情况：
由于BFS缘故，路径A上的点首先被确定状态。随后b->c依次被更新状态，但是路径B能得到更优的答案。
随后，路径B跟上来了。它更新了b的状态，b随后再次被放入处理队列中，依次而来的，b->c上面的点一个个地再次重新入队，再次被更新状态。

因此，使用SPFA进行类似最长路的DAG上dp时，每个点的最终状态跟拓扑序dp一样，会是最优的。这就是为什么SPFA能跑DAGdp的原因。
什么时候使用SPFA跑DAG会更好呢？确定了起点和终点的状况下。 如我原先所用的方法，我做了两遍FloodFill，又删了一遍点，还要作各种判断，才能避免其它点对拓扑序dp的干扰。但是使用SPFA，从起点开始松弛，直接松弛到终点的最优状态，它有效的兼顾了DAGdp所应该得到的最优状态，而又避免了拓扑序更新状态的条件之一——入度必须为0.因为这么做，显然会受到其它多余点（起点不能到的点/不能到终点的点）的干扰。
两者的复杂度如何呢？如果不考虑起点和终点的条件，拓扑序肯定更优。但如果考虑起点和终点的条件，综合考虑代码复杂度和时间复杂度，我觉得我应该会写SPFA。

感觉值得做个记录....qwq