Hanwan Space

差分约束简单入门

给您一连串的不等式组，让您找出满足该不等式的最大值或最小值。这就是差分约束要解决的问题。

引入

给出 nn 个变量和 mm 个不等式，就像这样

{x1−x2≤k1x3−x2≤k2x3−x1≤k3x4−x2≤k4x3−x2≤k5\begin{cases}x_1-x_2\le k_1\\x_3-x_2\le k_2\\x_3-x_1\le k_3\\x_4-x_2\le k_4\\x_3-x_2\le k_5\end{cases}

让您求出满足条件的 x1…x4x_1\dots x_4 中 x4−x1x_4-x_1 的最大值。

首先想到的就是手动推，很显然，计算机是不可能模拟手动推的。

与最短路算法的联系

考虑一下最短路算法的松弛过程。

cpp
if (dis[v] >= dis[u] + edge[i].val)
    dis[v] = dis[u] + edge[i].val;

这是不是很像上面的不等式？kk 就是边权，dis 数组就是那两个变量。但是符号是相反的。
这并不影响我们我们进行图论的建模。 我们只需要对于每个形如 xi−xj≤kx_i-x_j\le k 的不等式，从 jj 到 ii 连边，边权即为 kk 。 这样跑一遍从 11 到 nn 的最短路就是 xn−x1x_n-x_1 的最大值。

无解的情况

存在负环即无解。

在跑 SPFA 时记录一下每个点入队的次数，如果入队次数大于点数，即存在负环。

对于各种形式的不等式

  • 求最小值：需要把每个不等式转化为 xi−xj≥kx_i-x_j\ge k 的形式，从 jj 到 ii 连边，边权即为 kk 。然后跑一遍最长路即可。
  • 求最大值：需要把每个不等式转化为 xi−xj≤kx_i-x_j\le k 的形式，从 jj 到 ii 连边，边权即为 kk 。然后跑一遍最短路即可。
  • 没有等号的情况：如果是 xi−xj<kx_i-x_j<k 的形式，需要先转化为 xi−xj≤k−1x_i-x_j\le k-1 的形式连边。反之亦然。
  • 只有等号的情况：建双向边即可。即转化为 xi−xj≤kx_i-x_j\le k 和 xi−xj≥kx_i-x_j\ge k 的形式。

例题 1

[SCOI2011]糖果 传送门

思路

可以很轻易地根据差分约束系统建模。

这道题并不是求特定两个数之间的最小值，求得是最小值的总和，只需要把 dis 数组中的值加起来即为答案。

注意要开 long long，否则会 WA 一个点。

完整代码

cpp
#include <bits/stdc++.h>
 
using namespace std;
 
const int maxN = 1e5 + 5;
 
struct Edge {
	int next, to, val;
} edge[maxN << 1];
 
int head[maxN], neg[maxN];
int cnt, n, k;
bool used[maxN];
long long ans, dis[maxN];
queue<int> que;
 
void add(int from, int to, int val) {
	edge[++cnt] = (Edge) {head[from], to, val};
	head[from] = cnt;
}
 
bool lpfa() {
	while (!que.empty()) {
		int u = que.front();
		que.pop(); used[u] = false;
		for (int i = head[u]; ~i; i = edge[i].next) {
			int v = edge[i].to;
			if (dis[v] < dis[u] + edge[i].val) {
				dis[v] = dis[u] + edge[i].val;
				neg[v]++;
				if (neg[v] >= n) return false;
				if (!used[v]) {
					used[v] = true;
					que.push(v);
				}
			}
		}
	}
	return true;
}
 
int main() {
	memset(head, -1, sizeof(head));
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= k; i++) {
		int opt, a, b;
		scanf("%d%d%d", &opt, &a, &b);
		if (opt == 1) {add(a, b, 0); add(b, a, 0);}
		else if (opt == 2) add(a, b, 1);
		else if (opt == 3) add(b, a, 0);
		else if (opt == 4) add(b, a, 1);
		else if (opt == 5) add(a, b, 0);
		if ((opt == 2 || opt == 4) && a == b) {
			printf("-1\n");
			return 0;
		}
	}
	for (int i = 1; i <= n; i++) {
		neg[i]++, dis[i] = 1;
		used[i] = true;
		que.push(i);
	}
	if (!lpfa()) {
		printf("-1\n");
	} else {
		for (int i = 1; i <= n; i++)
			ans += dis[i];
		printf("%lld\n", ans);
	}
	return 0;
}

例题 2

种树 传送门

思路

如何建模？我们可以利用前缀和，建立 sum[b] 与 sum[e] 的关系。根据读入描述可建立模型 se−sb−1≥ts_e-s_{b-1}\ge t （为什么要减去 1？因为是闭区间 QwQ）。

其中还有一个隐含条件，就是每座房子前最多种一棵树，所以有了这样的不等式 0≤si−si−1≤10\le s_i-s_{i-1} \le 1，稍微转化一下就是两个不等式 si−si−1≥0s_i-s_{i-1}\ge 0 和 si−1−si≥−1s_{i-1}-s_i\ge -1。

需要建立一个超级源点向所有点连权值为 0 的边，这样从超级源点跑一遍最长路，最后 dis[n] 即为解。

完整代码

cpp
#include <bits/stdc++.h>
 
using namespace std;
 
const int maxN = 3e4 + 5;
const int INF = 0x3f3f3f3f;
 
struct Edge {
	int next, to, val;
} edge[maxN];
 
int head[maxN], dis[maxN];
int cnt, n, h;
bool used[maxN];
queue<int> que;
 
void add(int from, int to, int val) {
	edge[++cnt] = (Edge) {head[from], to, val};
	head[from] = cnt;
}
 
void lpfa(int s) {
	fill(dis, dis + n + 2, -INF);
	que.push(s);
	dis[s] = 0, used[s] = true;
	while (!que.empty()) {
		int u = que.front();
		que.pop(); used[u] = false;
		for (int i = head[u]; ~i; i = edge[i].next) {
			int v = edge[i].to;
			if (dis[v] < dis[u] + edge[i].val) {
				dis[v] = dis[u] + edge[i].val;
				if (!used[v]) {
					que.push(v);
					used[v] = true;
				}
			}
		}
	}
}
 
int main() {
	memset(head, -1, sizeof(head));
	scanf("%d%d", &n, &h);
	int s = n + 1;
	for (int i = 1; i <= h; i++) {
		int a, b, t;
		scanf("%d%d%d", &a, &b, &t);
		add(a - 1, b, t);
	}
	for (int i = 1; i <= n; i++) {
		add(i - 1, i, 0);
		add(i, i - 1, -1);
	}
	for (int i = 0; i <= n; i++)
		add(s, i, 0);
	lpfa(s);
	printf("%d\n", dis[n]);
	return 0;
}
  • 差分约束
© hawa130转载请注明出处
License: CC BY-NC-SA 4.0
上一篇

离散化 — 题解 for 程序自动分析

下一篇

树链剖分入门