一、定义
现有 \(n\) 个变量 \(a_1, a_2, ... ,a_n\)，给出 \(m\) 个不等式，第 \(i\) 个形如 \(a_i - a_j \leq k\)（ \(k\) 为常数， \(1 \leq i, j \leq m\) ），请构造出一组符合条件的数列 \(a\)。
二、解法
要求构造 \(a\)，直接暴力不好搞，时间复杂度也很高，考虑转化问题。
令 \(dis_i\) 为超级原点到节点 \(i\) 的最短路径长，如果一个节点 \(u\) 可以通过一条权值为 \(w\) 的边到达节点 \(v\) 的话，根据最短路径的性质，则一定满足 \(dis_v \leq dis_u + w\)。化简可得 \(dis_v - dis_u \leq w\)。与上述差分约束的不等式及其相似。所以当我们拿到一个不等式 \(a_i - a_j \leq k\) 时，可以在节点 \(j\) 和节点 \(i\) 间连接一条权值为 \(k\) 的有向边，再建立一个超级源点，求出到任意节点 \(i\) 的最短路径，便得到了一组答案。
当然，有时候题目中有隐藏的限制条件，这就因题而异了。
什么？你问怎么考虑无解的情况？还有无解的情况？！
是的，怎么考虑无解呢？
既然我们已经将问题转化成求解最短路了，所以只需要搞清楚最短路什么时候无解就行了。最短路无解的情况只有一种：图中存在 负环。
因此，Dijkstra 死掉了。所以处理差分约束类问题时，我们一般选择 SPFA 算法。设节点 \(i\) 入队次数为 \(num_i\)，则当 \(num_i \geq n\) 时，图中存在负环。
补充：常见的不等式转化方式如下：
若 \(a - b = k\)，转化为 \(a - b \leq k\) 且 \(a - b \geq k\)；
若 \(a - b > k\)，转化为 \(a - b \geq k + 1\)；
若 \(a - b < k\)，转为为 \(a - b \leq k - 1\)；
三、例题
1、差分约束系统
分析：
裸题，直接套用上述结论即可。
顺便挂个模板：
#include<bits/stdc++.h>
using namespace std;
#define SF scanf
#define PF printf
struct Edge {
int to, next, w;
}edge[50005];
struct node {
int dis, id;
};
int n, m, cnt, head[5005], num[5005], dis[5005];
bool vis[5005];
void add(int u, int v, int w) {
edge[++cnt].to = v;
edge[cnt].next = head[u];
edge[cnt].w = w;
head[u] = cnt;
}
void SPFA(int x) {
for(int i = 1; i <= n; i++) dis[i] = 0x3f3f3f3f;
dis[x] = 0;
queue<node> q;
q.push((node){0, x}), vis[x] = 1;
while(!q.empty()) {
node tmp = q.front();
q.pop();
vis[tmp.id] = 0;
num[tmp.id]++;
if(num[tmp.id] == n) {
PF("NO");
exit(0);
}
for(int i = head[tmp.id]; i; i = edge[i].next) {
int to = edge[i].to;
if(dis[to] > dis[tmp.id] + edge[i].w) {
dis[to] = dis[tmp.id] + edge[i].w;
if(!vis[to]) {
q.push((node){dis[to], to});
vis[to] = 1;
}
}
}
}
}
int main() {
SF("%d%d", &n, &m);
for(int i = 1; i <= n; i++) add(0, i, 0);
for(int i = 1; i <= m; i++) {
int u, v, w;
SF("%d%d%d", &u, &v, &w);
add(v, u, w);
}
SPFA(0);
for(int i = 1; i <= n; i++) PF("%d ", dis[i]);
return 0;
}
2、天平
分析：
显然输入给了我们很多不等式。
一共有 \(n\) 个砝码，设第 \(i\) 个砝码重 \(w_i\)（ \(1 \leq w_i \leq 3\) ）克。
现在已经给出了两个砝码 \(A\) 和 \(B\)。把它们放在了天平的一边，还需要另外两个砝码 \(C\) 和 \(D\)，放在天平的另一边。
因为 \(4 \leq n \leq 50\)，范围很小，可以直接对 \(C\) 和 \(D\)进行枚举。
要分别求出 \(w_A + w_B > w_C + w_D\)，\(w_A + w_B = w_C + w_D\) 和 \(w_A + w_B < w_C + w_D\)的方案数，设其分别为 \(c1\)、\(c2\)、\(c3\)。
关键在于怎样求出每一个 \(w_i\)，但这明显有点难，而且答案可能不唯一。
考虑对要求的三个不等式进行转化。
若要满足 \(w_A + w_B > w_C + w_D\)，即满足 \(w_A - w_C > w_D - w_B\) 或 \(w_A - w_D > w_C - w_B\) 即可。
如果 \(\min\{w_A - w_C\} > \max\{w_D - w_B\}\) 或 \(\min\{w_A - w_D\} > \max\{w_C - w_B\}\)，则一定满足第一个不等式。累计 \(c1\)。
其余两个不等式转化方式同上。
至此，问题转化为：对于任意的 \(i\) 和 \(j\)，设其满足条件的最小差值为 \(minn_{i,j}\)，满足条件的最大差值为 \(maxn_{i,j}\)，求解出所有的 \(minn\) 和 \(maxn\) 即可。
Code:
#include<bits/stdc++.h>
using namespace std;
#define SF scanf
#define PF printf
int Min[55][55], Max[55][55], n;
void floyd() {
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
if(i == k) continue;
for(int j = 1; j <= n; j++) {
if(j == k || i == j) continue;
Min[i][j] = max(Min[i][j], Min[i][k] + Min[k][j]); //求最小跑最长
Max[i][j] = min(Max[i][j], Max[i][k] + Max[k][j]); //求最大跑最短
}
}
}
}
int main() {
int A, B;
SF("%d%d%d", &n, &A, &B);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
char k;
cin >> k;
if(k == '+') Max[i][j] = 2, Min[i][j] = 1;
else if(k == '=' || i == j) Max[i][j] = Min[i][j] = 0;
else if(k == '-') Max[i][j] = -1, Min[i][j] = -2;
else Max[i][j] = 2, Min[i][j] = -2;
}
}
floyd(); //数据很小，保证有解，可以用 floyd
int c1 = 0, c2 = 0, c3 = 0;
for(int i = 1; i <= n; i++) {
if(i == A || i == B) continue;
for(int j = i + 1; j <= n; j++) {
if(j == A || j == B) continue;
if(Min[A][i] > Max[j][B] || Min[A][j] > Max[i][B]) c1++;
if((Max[A][i] == Min[A][i] && Min[A][i] == Min[j][B] && Min[j][B] == Max[j][B]) ||
(Max[A][j] == Min[A][j] && Min[A][j] == Min[i][B] && Min[i][B] == Max[i][B])) c2++;
if(Max[A][i] < Min[j][B] || Max[A][j] < Min[i][B]) c3++;
}
}
PF("%d %d %d", c1, c2, c3);
return 0;
}
3、Intervals
分析：
设前 \(i\) 个数中选了 \(d_i\) 个数。即要使每个 \(d_i\) 尽可能小。
对于第 \(i\) 个条件：\(l_i\) 到 \(r_i\) 中至少选择 \(w_i\) 个数。
即给出了 \(d_{r_i} - d_{l_i - 1} \geq w_i\) 这个限制条件。
转化成 \(d_{l_i - 1} - d_{r_i} \leq -w_i\)。就可以在 \(l_i - 1\) 和 \(r_i\) 之间连接权值为 \(-w_i\) 的有向边。
注意，这个题有隐藏条件！
你一定需要满足的条件是： \(0 \leq d_{i + 1} - d_i \leq 1\)。
再根据这个不等式建边就行了。
Code:
#include<bits/stdc++.h>
using namespace std;
#define SF scanf
#define PF printf
struct Edge {
int to, next, w;
}edge[200005];
int head[50005], cnt, dis[50005], n, s;
bool vis[50005];
void add(int u, int v, int w) {
edge[++cnt].to = v;
edge[cnt].next = head[u];
edge[cnt].w = w;
head[u] = cnt;
}
void SPFA(int x) {
queue<int> q;
q.push(x);
for(int i = 1; i <= s; i++) dis[i] = 0x3f3f3f3f;
vis[x] = 1, dis[x] = 0;
while(!q.empty()) {
int tmp = q.front();
q.pop();
vis[tmp] = 0;
for(int i = head[tmp]; i; i = edge[i].next) {
int to = edge[i].to;
if(dis[to] > dis[tmp] + edge[i].w) {
dis[to] = dis[tmp] + edge[i].w;
if(!vis[to]) {
vis[to] = 1;
q.push(to);
}
}
}
}
}
int main() {
SF("%d", &n);
for(int i = 1; i <= n; i++) {
int u, v, w;
SF("%d%d%d", &u, &v, &w);
u++, v++;
s = max(s, v);
add(v, u - 1, -w);
}
for(int i = 0; i < s; i++) add(i + 1, i, 0), add(i, i + 1, 1);
SPFA(s);
PF("%d", -dis[0]);
return 0;
}
4、矩阵游戏
分析：
调整法是个不错的方法。
首先我们可以先令第 \(n\) 行和第 \(m\) 列的元素都为 0 ，这样我们就能够得到一组答案 \(a\)，虽然此答案可能不合法，但我们可以在其基础上进行调整。
我们设一个变量 \(c\) ，易证在任意一行 \(i\) 中，将第 \(j\) 个元素 \(a_{i,j}\) 变为 \(a_{i,j} + (-1) ^ j * c\)，则该答案依旧合法。
再设一个变量 \(g\) ，易证在任意一列 \(r\) 中，将第 \(l\) 个元素 \(a_{l,r}\) 变为 \(a_{l,r} - (-1)^l * g\)，则该答案依旧合法。
这样对于任意一个元素 \(a_{i,j}\)，就将它变为了 \(a_{i,j} + c - g\) 或 \(a_{i,j} - c + g\)。
所以问题就转化成了：求解出各个行的 \(c\) 和各个列的 \(g\) 变量就可以了。
对其进行差分约束即可。
Code:
#include<bits/stdc++.h>
using namespace std;
#define SF scanf
#define PF printf
#define int long long
struct Edge {
int to, next, w;
}edge[500005];
int a[305][305], b[305][305], head[605], cnt, n, m, dis[605], num[605];
bool vis[100005];
void add(int u, int v, int w) {
edge[++cnt].to = v;
edge[cnt].next = head[u];
edge[cnt].w = w;
head[u] = cnt;
}
bool SPFA(int x) {
queue<int> q;
q.push(x);
for(int i = 1; i <= n + m; i++) dis[i] = 0x3f3f3f3f;
dis[x] = 0, vis[x] = 1;
while(!q.empty()) {
int tmp = q.front();
q.pop();
vis[tmp] = 0;
for(int i = head[tmp]; i; i = edge[i].next) {
int to = edge[i].to;
if(dis[to] > dis[tmp] + edge[i].w) {
dis[to] = dis[tmp] + edge[i].w;
if(++num[to] >= n + m) return false;
if(!vis[to]) {
vis[to] = 1;
q.push(to);
}
}
}
}
return true;
}
signed main() {
freopen("matrix.in", "r", stdin);
freopen("matrix.out", "w", stdout);
int t;
SF("%lld", &t);
while(t--) {
cnt = 0;
memset(head, 0, sizeof(head));
memset(vis, 0, sizeof(vis));
memset(num, 0, sizeof(num));
SF("%lld%lld", &n, &m);
for(int i = 1; i < n; i++) {
for(int j = 1; j < m; j++) SF("%lld", &b[i][j]);
}
for(int i = n - 1; i; i--) {
for(int j = m - 1; j; j--) a[i][j] = b[i][j] - a[i + 1][j] - a[i][j + 1] - a[i + 1][j + 1];
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if((i + j) & 1) {
// 0 <= aij + ci - gj <= 1e6
add(i, j + n, a[i][j]);
add(j + n, i, 1e6 - a[i][j]);
}
else {
// 0 <= aij - ci + gj <= 1e6
add(j + n, i, a[i][j]);
add(i, j + n, 1e6 - a[i][j]);
}
}
}
bool flag = SPFA(1);
if(!flag) {
PF("NO\n");
continue;
}
PF("YES\n");
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if((i + j) & 1) PF("%lld ", a[i][j] + dis[i] - dis[j + n]);
else PF("%lld ", a[i][j] - dis[i] + dis[j + n]);
}
PF("\n");
}
}
return 0;
}
