差分约束

定义

差分约束系统 是一种特殊的元一次不等式组，它包含个变量以及个约束条件，每个约束条件是由两个其中的变量做差构成的，形如，其中并且是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解，使得所有的约束条件得到满足，否则判断出无解。

差分约束系统中的每个约束条件都可以变形成，这与单源最短路中的三角形不等式非常相似。因此，我们可以把每个变量看做图中的一个结点，对于每个约束条件，从结点向结点连一条长度为的有向边。

注意到，如果是该差分约束系统的一组解，那么对于任意的常数，显然也是该差分约束系统的一组解，因为这样做差后刚好被消掉。

过程

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

性质

一般使用 Bellman-Ford 或队列优化的 Bellman-Ford（俗称 SPFA，在某些随机图跑得很快）判断图中是否存在负环，最坏时间复杂度为。

常用变形技巧

例题 luogu P1993 小 K 的农场

题目大意：求解差分约束系统，有条约束条件，每条都为形如，或的形式，判断该差分约束系统有没有解。

题意	转化	连边
		`add(a, b, -c);`
		`add(b, a, c);`
		`add(b, a, 0), add(a, b, 0);`

跑判断负环，如果不存在负环，输出 Yes，否则输出 No。

参考代码

例题 P4926[1007]倍杀测量者

不考虑二分等其他的东西，这里只论述差分系统的求解方法。

对每个和取一个就可以把乘法变成加法运算，即，这样就可以用差分约束解决了。

Bellman-Ford 判负环代码实现

下面是用 Bellman-Ford 算法判断图中是否存在负环的代码实现，请在调用前先保证图是连通的。

实现

=== "C++"

```cpp
bool Bellman_Ford() {
  for (int i = 0; i < n; i++) {
    bool jud = false;
    for (int j = 1; j <= n; j++)
      for (int k = h[j]; ~k; k = nxt[k])
        if (dist[j] > dist[p[k]] + w[k])
          dist[j] = dist[p[k]] + w[k], jud = true;
    if (!jud) break;
  }
  for (int i = 1; i <= n; i++)
    for (int j = h[i]; ~j; j = nxt[j])
      if (dist[i] > dist[p[j]] + w[j]) return false;
  return true;
}
```

=== "Python"

```python
def Bellman_Ford():
    for i in range(0, n):
        jud = False
        for j in range(1, n + 1):
            while ~k:
                k = h[j]
                if dist[j] > dist[p[k]] + w[k]:
                    dist[j] = dist[p[k]] + w[k]; jud = True
                k = nxt[k]
        if jud == False:
            break
    for i in range(1, n + 1):
        while ~j:
            j = h[i]
            if dist[i] > dist[p[j]] + w[j]:
                return False
            j = nxt[j]
    return True
```