差分约束学习笔记

\(n\) 个未知数，\(m\) 组形如 \(x_i-x_j \le y_k\) 的不等式，求可行解。

对于每一个 \(x_i\)，我们都能找到 \(a\) 组关于它的不等式，第 \(j\) 形如为 \(x_i-x_{b_j} \le y_{c_j}\)。

\(\therefore x_i \le \min(x_{b_1}+y_{c_1},x_{b_2}+y_{c_2},......,x_{b_a}+y_{c_a})\)

该不等式取等时 \(x_i= \min(x_{b_1}+y_{c_1},x_{b_2}+y_{c_2},......,x_{b_a}+y_{c_a})\)

我们发现最短路求 \(dis_u\) 的式子与上面的式子非常相似：在一张有向图中，若有 \(a\) 个点可以直接到达点 \(u\)，第 \(i\) 个点为 \(v_i\) 则 \(dis_u= \min(dis_{v_1}+w(u,v_1),dis_{v_2}+w(u,v_2),......dis_{v_a}+w(u,v_a))\)

所以考虑通过最短路求可行解。

不难想到先对于每一个不等式 \(x_i-x_j \le y_k\)，从 \(j\) 向 \(i\) 连一条权值为 \(y_k\) 的边；再建一个 \(0\) 号点向 \(n\) 个点连 \(1\) 条权值为 \(0\) 的边，这相当于添加了 \(n\) 个条件：对于任意一个 \(i \in [1,n]\)，\(x_i \le x_0\)。

那么经过上面的操作后，我们就可以从 \(0\) 号点为起点跑一遍单源最短路，\(dis_i\) 即为 \(x_i\) 的一个可行解。

我们注意到 \(x_i\) 并不一定存在可行解，思考一下 \(x_i\) 没有解当且仅当存在若干个 \(x_j(j \ne i)\) 的解和 \(x_i\) 的解相互矛盾，即图中出现了负环，判一下就好了。

模板：luogu P5960