数学和图论的完美结合——差分约束

· · 算法·理论

由于作者觉得差分约束很好玩，所以心血来潮写了个记录。

Part 0：前置芝士

Part 1：什么是差分约束？

其实差分约束跟差分没有什么关系。

我们将形如这样的不等式组称为差分约束系统：

\begin{cases} x_{c_1} - x_{c'_1} \leq k_1 \\ x_{c_2} - x_{c'_2} \leq k_2 \\ \cdots \\ x_{c_m} - x_{c'_m }\leq k_m \end{cases}

其中包含 m 个不等式约束和 n 个未知变量。

一般的，我们的任务就是找到这个不等式组的一组整数解。

举个例子：

\begin{cases} x_2 - x_1 \leq 3 \\ x_3 - x_2 \leq 2 \\ x_1 - x_3 \leq -4\end{cases}

我们很容易就能找到一组解，比如 x_1 = 1，x_2 = 3，x_3 = 5。但是，如果我们探索一下更多的解，就会发现：k 取任意整数时，x_1 = k + 1，x_2 = k + 3，x_3 = k + 5 都是这个不等式组的一组解。

我们称 x_1 = 1，x_2 = 3，x_3 = 5 这样的解为“特解”，而像 x_1 = k + 1，x_2 = k + 3，x_3 = k + 5 这样的解被称为“通解”。

Part 2：如何求解差分约束？

Part 2.1：最短路解法

我们首先可以将不等式组转换一下。

对于一个不等式组其中的一个不等式 x_i - x_{j} \leq k（其中 1 \leq i \neq j \leq n），我们可以进行移项。那么这个不等式就变成了 x_i \leq x_j + k。

学过 SPFA 的都知道，SPFA 算法中有一个性质，就是三角不等式。对于起点 s 和两个点 u, v，满足 \text{dis}_v \leq \text{dis}_u + w_{(u, v)}。

你会发现，这些变量可以全部对应。那么，差分约束是否可以用最短路解决呢？答案是可以。

那么我们容易得出以下最短路连边方法：

::::success[结论 1.1]{open} 对于一个不等式 x_i - x_j \leq k，在用最短路解决的情况下，需连一条 j \to i 的边，边权为 k。 ::::

那么我们可以把每一个未知量都看成一个顶点。此外，我们为了保证图联通，我们需要建立一个超级源点，一般情况下为 0 号点，它连向每个除了自身的顶点，边权为 0。

一般情况下，在有解的时候，不等式组的解如下：

::::success[结论 2.1]{open} 对于一个不等式组的未知量 x_1, x_2, \cdots, x_n，在有解时有这样一组特解：x_i = \text{dis}_i。其中 \text{dis}_i 是以 0 号点为起点到 i 号点的最短路径长度。 ::::

这时候你肯定会问，那么怎么判定无解呢？

你可能会猜想，负环就是无解的情况。我们先别急于解决，我们先举个例子。

例如这组不等式组：

\begin{cases} x_2 - x_1 \leq 3 \\ x_3 - x_2 \leq 2 \\ x_1 - x_3 \leq -6 \end{cases}

我们先来解一下这个不等式组。

由 x_2 - x_1 \leq 3，得 x_2 \leq x_1 + 3。代入 x_3 - x_2 \leq 2，得 x_3 \leq (x_1 + 3) + 2 = x_1 + 5。最后，将 x_3 \leq x_1 + 5 代入 x_1 - x_3 \leq -6，得到 x_1 \leq (x_1 + 5) - 6 = x_1 - 1。

很显然，x_1 \leq x_1 - 1 是恒不成立的，所以这个不等式组无解。

解完不等式组后，我们进行连边：

我们发现，图中确实存在负环。

于是我们的得到结论 3：

::::success[结论 3.1]{open} 对于一组不等式组，在用最短路解决的情况下，如果构图后图中有负环，那么不等式组无解。 ::::

有人会问，这只是举了个例子，有没有详细一点的？

当然，作者用另外一种方法讲一下：由于 \text{dis} 数组是不等式组的一组特解，那么只需判定最短路是否无解即可。那么最短路什么时候无解？当然是有负环了！

什么，你不知道怎么判负环？我来讲讲，因为 SPFA 每次会将一个点放进队列里，并对这个点所有地出边进行松弛。如果这个点地进队次数超过了 n，说明松弛次数太多，有负环。

所以，我们只需要记录每个点的入队次数并进行判断即可。

Part 2.2：最长路算法

欸，作者？你前文提到了最短路，那最长路可以解决吗？最长路也可以的。

我们将不等式变成另外一个形式：x_j \leq x_i - k。

由最短路算法同理可得以下结论：

::::success[结论 1.2]{open} 对于一个不等式 x_i - x_j \leq k，在用最长路解决的情况下，需连一条 i \to j 的边，边权为 -k。 ::::

::::success[结论 2.2]{open} 对于一个不等式组的未知量 x_1, x_2, \cdots, x_n，在有解时有这样一组特解：x_i = \text{dis}_i。其中 \text{dis}_i 是以 0 号点为起点到 i 号点的最长路径长度。 ::::

::::success[结论 3.2]{open} 对于一组不等式组，在用最长路解决的情况下，如果构图后图中有正环，那么不等式组无解。 ::::

Part 3：例题

P5960 【模板】差分约束

模板题，按照步骤解决即可。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int kMaxN = 5e6 + 10;

int n, m, s, v[kMaxN], cnt[kMaxN], dis[kMaxN];
vector<pair<int, int>> e[kMaxN];

string SPFA() {
  fill(dis, dis + n + 1, 2147483647);
  queue<int> q;
  dis[0] = 0, v[0] = 1;
  for (q.push(0); q.size(); ) {
    int x = q.front();
    q.pop();
    v[x] = 0;
    for (auto i : e[x]) {
      if (dis[i.first] > dis[x] + i.second) {
        dis[i.first] = dis[x] + i.second;
        if (v[i.first]) {
          continue;
        }
        v[i.first] = 1;
        q.push(i.first);
        ++ cnt[i.first];
        if (cnt[i.first] > n) {
          return "NO";
        }
      }
    }  
  }
  return "YES";
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; ++ i) {
    e[0].push_back({i, 0});
  }
  for (int i = 1, u, v, w; i <= m; ++ i) {
    cin >> u >> v >> w;
    e[v].push_back({u, w});
  }
  string t = SPFA();
  if (t == "NO") {
    cout << t << '\n';
  } else {
    for (int i = 1; i <= n; ++ i) {
      cout << dis[i] << ' ';
    }
    cout << '\n';
  }
  return 0; 
}

P1993 小 K 的农场

首先将题目的三种形式转换成不等式形式：

前两种很好解决，那么第三种呢？很简单，只需转换成 x_a - x_b \leq 0 且 x_a - x_b \geq 0 即可。

于是不等式移项并变形后变成这样：

那么接下来就很好解决了。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int kMaxN = 5e6 + 10;

int n, m, s, v[kMaxN], cnt[kMaxN], dis[kMaxN];
vector<pair<int, int>> e[kMaxN];

string SPFA() {
  fill(dis, dis + n + 1, 2e9);
  queue<int> q;
  dis[0] = 0, v[0] = 1;
  for (q.push(0); q.size(); ) {
    int x = q.front();
    q.pop();
    v[x] = 0;
    for (auto i : e[x]) {
      if (dis[i.first] > dis[x] + i.second) {
        dis[i.first] = dis[x] + i.second;
        if (v[i.first]) {
          continue;
        }
        v[i.first] = 1;
        q.push(i.first);
        ++ cnt[i.first];
        if (cnt[i.first] > n) {
          return "No";
        }
      }
    }  
  }
  return "Yes";
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; ++ i) {
    e[0].push_back({i, 0});
  }
  for (int i = 1, op, u, v, w; i <= m; ++ i) {
    cin >> op;
    if (op == 1) {
      cin >> u >> v >> w;
      e[u].push_back({v, -w}); 
    } else if (op == 2) {
      cin >> u >> v >> w;
      e[v].push_back({u, w});
    } else {
      cin >> u >> v;
      e[u].push_back({v, 0});
      e[v].push_back({u, 0});
    }
  }
  cout << SPFA() << '\n'; 
  return 0; 
}

P2294 [HNOI2005] 狡猾的商人

其实前面那一段文字都是没有什么用的。

显然，看到总收入和一段时间，我们就可以想到前缀和数组 \text{sum}。

所以，我们将从第 s 个月到第 t 个月的总收入为 v 转换为 \text{sum}_t - \text{sum}_{s - 1} = v。

同样的，根据上一题的解法，我们可以把这个式子拆成两个不等式：

\begin{cases} \text{sum}_t - \text{sum}_{s - 1} \leq v \\ \text{sum}_t - \text{sum}_{s - 1} \geq v \end{cases}

变形，得：

\begin{cases} \text{sum}_t \leq \text{sum}_{s - 1} + v \\ \text{sum}_{s - 1} \leq \text{sum}_t + v \end{cases}

于是我们只需要连两条边：

这里有一个特别需要注意的点，s - 1 有可能为 0，那么 s - 1 会占用超级源点的位置。我们有两种解决方法，把超级源点设为 n + 1 或连边时把 s, t 都加上 1。

改完之后还要注意，点数会变为 n + 1，所以在某些地方我们还需要更改。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int kMaxN = 5e6 + 10;

int n, m, s, v[kMaxN], cnt[kMaxN], dis[kMaxN];
vector<pair<int, int>> e[kMaxN];

string SPFA() {
  fill(dis, dis + n + 2, 2147483647);
  queue<int> q;
  dis[0] = 0, v[0] = 1;
  for (q.push(0); q.size(); ) {
    int x = q.front();
    q.pop();
    v[x] = 0;
    for (auto i : e[x]) {
      if (dis[i.first] > dis[x] + i.second) {
        dis[i.first] = dis[x] + i.second;
        if (v[i.first]) {
          continue;
        }
        v[i.first] = 1;
        q.push(i.first);
        ++ cnt[i.first];
        if (cnt[i.first] > n + 1) {
          return "false";
        }
      }
    }  
  }
  return "true";
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> n >> m;
    for (int i = 1; i <= n + 1; ++ i) {
      e[0].push_back({i, 0});
    }
    for (int i = 1, u, v, w; i <= m; ++ i) {
      cin >> u >> v >> w;
      ++ u, ++ v;
      e[u - 1].push_back({v, w});
      e[v].push_back({u - 1, -w});
    }
    cout << SPFA() << '\n';
    for (int i = 1; i <= n + 1; ++ i) {
      e[i].clear();
      cnt[i] = v[i] = 0;
    }
  }
  return 0; 
}

Part 4：差分约束的变式

由于篇幅太长，所以这里只写一个典型的变式问题。

因为这些问题没有太系统化的总结，所以我们用例题 P4878 [USACO05DEC] Layout G 来讲一讲。

第一眼：差分约束模板。

第二眼：1 号奶牛与 N 号奶牛间的最大距离？还可以距离无穷远？

先别急，我们先来建边。

首先看到最大距离，就知道要跑最短路了。

设第 i 个奶牛的位置为 X_i，那么好基友的条件可以转换为：X_A - X_B \leq D（即 X_A \leq X_B + D），情敌的条件可以转换为：X_A - X_B \ge D（即 X_B \leq X_A - D）。这样连边部分就解决了。

没有合法方案的情况很简单，我们先从 0 号源点跑 SPFA 判断一下负环。

重点来了，我们需要跑两次最短路，第二次需要从 1 号点开始跑。为啥？因为队列最前面的是 1 号奶牛。

那跑完了之后干啥？这里我们就需要知道一个结论了：

::::success[结论 4.1]{open} 对于一个不等式组，在有解的情况下，\max(x_n - x_1) = \text{dis}_n，其中 \text{dis}_n 是以 1 号点为起点到 n 号点的最短路径长度。 ::::

欸？有时候 \text{dis}_n = \infty，你也没告诉我怎么办啊？这种情况下图不联通，正好对应距离可以无穷大的情况。

那么这道题就做完了。但是，这里作者要增加一个结论。我们通过结论 4.1 对称及推导之后可以得到：

::::success[结论 4.2]{open} 对于一个不等式组，在有解的情况下，\min(x_n - x_1) = \text{dis}_n，其中 \text{dis}_n 是以 1 号点为起点到 n 号点的最长路径长度。 ::::

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int kMaxN = 5e6 + 10;

int n, ml, md, v[kMaxN], cnt[kMaxN], dis[kMaxN];
vector<pair<int, int>> e[kMaxN];

bool SPFA(int s) {
  fill(dis, dis + n + 1, 2e9);
  queue<int> q;
  dis[s] = 0, v[s] = cnt[s] = 1;
  for (q.push(s); q.size(); ) {
    int x = q.front();
    q.pop();
    v[x] = 0;
    for (auto i : e[x]) {
      if (dis[i.first] > dis[x] + i.second) {
        dis[i.first] = dis[x] + i.second;
        if (v[i.first]) {
          continue;
        }
        v[i.first] = 1;
        q.push(i.first);
        ++ cnt[i.first];
        if (cnt[i.first] >= n) {
          return 0;
        }
      }
    }  
  }
  return 1;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> ml >> md;
  for (int i = 1; i <= n; ++ i) {
    e[0].push_back({i, 0});
  }
  for (int i = 1, u, v, w; i <= ml; ++ i) {
    cin >> u >> v >> w;
    e[u].push_back({v, w});
  }
  for (int i = 1, u, v, w; i <= md; ++ i) {
    cin >> u >> v >> w;
    e[v].push_back({u, -w});
  }
  for (int i = 1; i < n; ++ i) {
    e[i + 1].push_back({i, 0});
  }
  if (!SPFA(0)) {
    return cout << "-1\n", 0;
  }
  SPFA(1);
  cout << (dis[n] >= 2e9? -2 : dis[n]) << '\n';
  return 0; 
}

Part 5：总结

其实差分约束相对于其他图论问题还是好理解一些的（至少作者是这么认为）。

差分约束的题基本可以分为四个步骤：

  1. 找出不等关系；
  2. 不等式推导变形；
  3. 跑最短路；
  4. 输出对应的答案（如求出解、求最大值）。

而差分约束的重点就是第一步和第二步，所以大家一定要锻炼自己推导不等式组的能力。

那么就讲到这里了，下课！