负环、差分约束和传递闭包

差分约束

https://oi-wiki.org/graph/diff-constraints/

定义

差分约束系统 是一种特殊的 \(n\) 元一次不等式组，它包含 \(n\) 个变量 \(x_1,...,x_n\) 以及 \(m\) 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 \(x_i - x_j \le c_k\)，其中 \(1 \le i, j \le n, i \neq j, 1 \le k \le m\) 并且 \(c_k\) 是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解 \(x_1=a_1,...,x_n=a_n\)，使得所有的约束条件得到满足，否则判断出无解。

差分约束系统中的每个约束条件 \(x_i - x_j \le c_k\) 都可以变形成 \(x_i \le x_j + c_k\)，这与单源最短路中的三角形不等式 \(dist[y] \le dist[x] + z\) 非常相似。因此，我们可以把每个变量 看做图中的一个结点，对于每个约束条件 \(x_i - x_j \le c_k\)，从结点 \(j\) 向结点 \(i\) 连一条长度为 \(c_k\) 的有向边。

注意到，如果 \(\{a_1, ..., a_n\}\) 是该差分约束系统的一组解，那么对于任意的常数 \(d\)，\(\{a_1+d, ..., a_n+d\}\) 显然也是该差分约束系统的一组解，因为这样做差后 \(d\) 刚好被消掉。

过程

设 \(dist[0] = 0\) 并向每一个点连一条权重为 \(0\) 边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则，\(x_i = dist[i]\) 为该差分约束系统的一组解。

时间复杂度 \(O(nm)\)。

原理

对于一个环，假设两个相邻点编号为 \(i,j\)。如果存在负环，那么 \(w_i - w_j \le a_1\)，\(w_i - w_j \ge -a_2\)，且 \(a_1 + a_2 < 0\)，也即 \(a_1 \le -a_2\)。显然矛盾。

否则，对于 \(w_i - w_j \le a\)，在图上体现了 \(d_i \le d_j + a\) 的限制。（从 \(j\) 连向 \(i\)）而 \(d_i\) 体现为 \(0\) 到 \(i\) 的距离。

扩展

考虑差分约束系统 \(\cfrac{w_i}{w_j} \le c_k\) 的求解方式。就是把每个数字取 \(\log\) 即可。

传递闭包

floyd，但是每条边表示某一种关系 \(rel_{i, j}\)。对于 \(rel_{i, j}\) 和 \(rel_{j, k}\)，可以维护将其合并到 \(rel_{i, k}\)。