关于差分约束系统中跑最长路还是最短路的澄清

· · 个人记录

关于差分约束系统中跑最长路还是最短路的澄清

0x01 前置知识

差分约束系统基础【原理、建图】

最短路及负环【主要掌握SPFA】

大家应该都会吧

0x02 错误示范

现在我们需要利用差分约束系统求解 最小解集

注意到，由于最短路跑出来一定满足 d_v <= d_u + w_{u,v} ，这里 d_v 必然是所有可行的入边中距离最小的（在最短路求解过程中会被不断松弛成最短），即满足条件的理论最小值

故用最短路跑最小解集，同理用最长路跑最大解集

0x03 错误原因

要想知道它为什么不对，我们需要深刻理解差分约束系统的原理

事实上，最短路/最长路求解出的看上去是最小/最大的解，实际只是真实解集的必要区间

众所周知，为了使每个未知量满足题设线性不等式，我们需要利用到最短路/最长路的松弛操作（下面以最短路的松弛为例）

if (dis[v] > dis[u] + w) dis[v] = dis[u] + w;

松弛操作本质上的结果就是使 d_v 满足所有线性不等式 d_u + w >= d_v ，这显然可以满足题设的约束。但考虑这个 d_v 理论可以更小吗？答案是肯定的，因为根据题设只需要 d_u + w >= d_v 即可，这里的 d_v （至少在这里）是无下界的；但在最短路里可以更小吗？答案是否定的，因为最短路一定是要找到一个确切的 d_u + w == d_v 才作更新，而需要用来更新的更小的 d_v 的边在图中并不存在（实际显然无法做到全部存在）

举个栗子，我们可以把最短路的松弛过程简化成 找一个 x 使 x <= \{ 5, 2, 3, 1, 4 \} 中的任一元素。最短路找到的一定是 1，因为在这个已知的有限集合里没有元素比 1 还小了。但实际上 x 可以取 ( -\infty,1 ] 中的任何一个数。

反而，我们会发现最短路求出来的居然其实是最大值：考虑如果 d_v 大一点，那就一定不满足所有的约束条件 d_u + w >= d_v，所以这里的 d_v 是最大的解。

因此，最短路跑出来的是满足题设条件的最大的解集！

同理，最长路跑出来的是满足题设条件的最小的解集！

0x03 总结一下

差分约束系统所利用的最短路松弛来求解，一定程度上是有缺陷的——解出来的值仅限于题设给定的所有约束中（毕竟你一个最短路它每个节点的距离肯定是实际可到的），故一定要理性分析

再强调一下：

要想求最小解集跑最长路；要想求最大解集跑最短路