差分约束

目录

• 写在前面
• 开始闲聊
  • 原理
  • 有无解情况
  • 最小值问题
  • 不等式标准化
• 例题
• 几个习题
• 习题题解：
  • Intervals
  • 糖果
  • 排队布局
• 写在最后

写在前面

这里主要记一下自己对差分约束的理解

因为更详细的解释都在学姐博客里有，我就不搬过来了（主要是我懒

Update2021.01.31 近期又刷了一批差分约束题目，对以前的叙述做了调整

开始闲聊

感觉差分约束很像一个利用数学中的不等式求最短路的东东（或者说利用最短路求数学不等式的解的范围

说实话，我想用差分约束做一下昨天考试的数学试卷中一个求不等式范围的题

原理

在我们的众多最短路板子中，这样一个式子一定不陌生吧

\[dis[v] > dis[u] + e[i].w \]

这就是最短路的松弛操作，也是差分约束能将不等式转化为图论的基本
那么所有的不等关系都能转化成类似的形式。建图后再根据需要跑最短路即可，也可以把 \(>\) 改为 \(<\) 跑最长路，不过不等关系的形式也要发生相应的转换

目前我遇到的有关差分约束的题套路基本相同：

• 根据题目的表面意思找出表面的不等关系式，或者构造出不等关系式
• 还有一些是根据题目背景或实际情况，找到题目中隐含的不等关系式

其他的操作和最短路类似了

有无解情况

在差分约束中需要判断有无解的情况：如果不能满足所有约束条件，建图来的图会有负环

这个用 $\text {SPFA} $ 或者 \(\text {dfs_SPFA}\)就可以办到

关于 $\text {SPFA} $ ，他死了

最小值问题

“如果我们把不等式的符号改变一下那么求得最短路那不就是变成了最长路问题吗，

那么我们在做题的时候只需要把 \(\text {spfa}\) 中的松弛操作的符号变一下就行了....”- \(Kersen\)

不等式标准化

利用我们所学过的小学二年级知识即可轻松解决

1、如果不等式方向不对，可以乘-1

2、如果是个等式 \(a-b=c\)，可以化成两个不等式

\[a-b \le c \]

\[a-b \ge c \]

3、如果只有 \(>\)，如 \(a - b < c\)，我们可以这样

\[a-b \le c - 1 \]

例题

luogu模板题

利用上述内容轻松切掉它吧

Code

//通过不等式建边求最短路？ 
#include
#include
#include
#include
using namespace std;
const int MAXN = 5e3+5;
struct egde{
	int to,nxt,w;
}e[MAXN];
struct node{
	int point,dis;
	bool operator < (const node & b) const {return dis > b.dis; }
};
int head[MAXN],num_edge;
int n, m;
int dis[MAXN],id[MAXN],sum[MAXN];
bool flag,vis[MAXN];
queue q;

void add(int from,int to,int w){
	e[++num_edge].nxt = head[from];
	e[num_edge].to = to;
	e[num_edge].w = w;
	head[from] = num_edge;
}

void spfa(){
	for(int i=1;i<=n;++i){
		if(!id[i]){
			q.push(i);
			dis[i] = 0;
		}
	}
	while(!q.empty()){
		int u = q.front(); q.pop();
		vis[u] = 0;
		if(++sum[u] > n){
			 printf("NO");
			 flag = 1;
			 return ;
		}
		for(int i = head[u]; i; i = e[i].nxt){
			int v = e[i].to;
			if(dis[u] + e[i].w < dis[v]){
				dis[v] = dis[u] + e[i].w;
				if(!vis[v])
				q.push(v);
			}
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,u,v,w;i<=m;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(v,u,w);
		id[u]++;
	}
	memset(dis, 0x3f, sizeof(dis));
	spfa();
	if(flag)return 0;
	for(int i=1;i<=n;++i){
		printf("%d ",dis[i]);
	}
	return 0;
}

几个习题

#10087 「一本通 3.4 例 1」Intervals
#10088 「一本通 3.4 例 2」出纳员问题
#10089 「一本通 3.4 练习 1」糖果
#10090 「一本通 3.4 练习 2」排队布局

习题题解：

Intervals

luogu题目网址
Loj题目网址

Solution

设 \(d[i]\) 表示 \(0 \sim i\) 中共选了 \(d[i]\) 个数，\(c_i\) 表示第 \(i\) 个区间需要 \(c_i\) 个数。
根据题目给我们的闭区间 \([a_i,b_i]\) 的要求，不难得到么一个约束条件

\[d[b_i]-d[a_i-1]>=c_i \]

发现选数时，一个数只能被选一次，我们又可以得到一个约束条件

\[0 \le d[i] - d[i - 1] \le 1 \]

根据我们所好随便改成松弛操作的形式求最短路/最长路即可

Code

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp Ak IOI"< q;

int read(){
	int s = 0, w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
	return s * w;
}

void add_edge(int from, int to, int w){	e[++num_edge] = (edge){to, w, head[from]}, head[from] = num_edge; }

int SPFA(int st){
	for(int i = minn; i <= maxm; ++i) dis[i] = INF;
	q.push(st);
	vis[st] = true;
	dis[st] = 0;
	while(!q.empty()){
		int t = q.front(); q.pop();
		vis[t] = false;
		for(int i = head[t]; i; i = e[i].nxt){
			int v = e[i].to;
//			cout< dis[t] + e[i].w){
				dis[v] = dis[t] + e[i].w;
				if(!vis[v]) q.push(v), vis[v] = true;
			}
		}
	}
	return -dis[maxm];
}

int main()
{
	n = read();
	for(int i = 1, u, v, w; i <= n; ++i){
		u = read(), v = read(), w = read();
		add_edge(u - 1, v, -w);//根据我们推出来的约束条件加边即可
		maxm = max(v, maxm);
		minn = min(u - 1, minn);
	}
	for(int i = minn; i <= maxm; ++i) add_edge(i, i + 1, -0), add_edge(i + 1, i, 1);
	printf("%d", SPFA(minn));
	return 0;
}

糖果

luogu题目网址
Loj题目网址

Solution

这个题意更裸，把每个小朋友看做结点就好了，其他处理类似于上面的不等式标准化去变换就好

不过，约束条件到是很好确定了，从哪开始跑最短路呢？

既然是让老师发糖，就让老师做一个超级大源点 \(x_0\) 吧，老师和每个学生 \(x_i\) 的约束条件是

\[x_i - x_0 \ge 1 \]

毕竟每个小孩都要吃糖

但是，你以为正着跑一遍建边就能过吗？
太天真了！
江湖上早就有 \(\text {SPFA}\)已死的说法
出题人肯定想变着法的卡你，所以换个思路吧，反着建图，会提高不少效率/xyx
我怎么知道的？过来人我不知道？

Code

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include
#include
#include
#include
#include
#define int long long
#define orz cout<<"lkp AK IOI!"< q;

int read(){
	int s = 0, f = 0;
	char ch = getchar();
	while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
	return f ? -s : s;
}

void add_edge(int from, int to, int w){ e[++num_edge] = (edge){to, w, head[from]}, head[from] = num_edge; }

void SPFA(){
	memset(dis, 0x3f, sizeof dis);
	q.push(0);
	vis[0] = true;
	dis[0] = 0;
	while(!q.empty()){
		int u = q.front(); q.pop();
		vis[u] = false;
		if(cnt[u] == n - 1) {flag = 1; return ;}
		cnt[u]++;
		for(int i = head[u]; i; i = e[i].nxt){
			int v = e[i].to;
			if(dis[v] > dis[u] + e[i].w){
				dis[v] = dis[u] + e[i].w;
				if(!vis[v]) q.push(v), vis[v] = true;
			}
		}
	} 
}

signed main()
{
	n = read(), m = read();
	for(int i = 1, x, u, v; i <= m; ++i){
		x = read(), u = read(), v = read(); 
		if(x == 1) add_edge(u, v, 0), add_edge(v, u, 0);
		else if(x == 2) {add_edge(u, v, -1); if(u == v){printf("-1"); return 0;} }
		else if(x == 3) add_edge(v, u, 0);
		else if(x == 4) {add_edge(v, u, -1); if(u == v){printf("-1"); return 0;} }
		else if(x == 5) add_edge(u, v, 0);
	}
	for(int i = n; i >= 1; --i) add_edge(0, i, -1);
	//为什么反着建会变快？？？sb出题人卡我？
	SPFA();
	if(flag) puts("-1");
	else {
		int ans = 0;
		for(int i = 1; i <= n; ++i) ans -= dis[i];
		printf("%lld\n", ans);
	}
	return 0;
}

排队布局

luogu题目网址
Loj题目网址

Solution

同样可以根据题目输入搞出几个约束条件

如果是基友，所以可以这样构造：

\[P_B - P_A \le D \]

如果是情敌，所以可以这样构造：

\[P_B - P_A \ge D \]

因为每个奶牛是序号是挨着的，存在负权环，像这样

（借用一下BinDir0大佬的图）

所以会有这个隐含条件

\[P_{i+1} - P_i \le 0 \]

不过洛谷上有几组Hack数据还会将我们干掉

所以我们还要连一个超级大源点，从 \(0\) 跑判断有无解，从 \(1\) 跑计算结果

\[P_i - P_0 \le 0 \]

Code

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"< q;

int read(){
	int s = 0, f = 0;
	char ch = getchar();
	while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
	return f ? -s : s;
}

void add_edge(int from, int to, int w){ e[++num_edge] = (edge){to, w, head[from]}, head[from] = num_edge; }

void SPFA(int st){
	for(int i = 1; i <= n; ++i) dis[i] = -INF;
//	memset(dis, -0x3f, sizeof dis);
	memset(vis, false, sizeof vis);
	dis[st] = 0; vis[st] = true;
	q.push(st);
	while(!q.empty()){
		int u = q.front(); q.pop();
		vis[u] = false;
		cnt[u] ++;
		if(cnt[u] == n + 1) { flag = true; return ;}
		for(int i = head[u]; i; i = e[i].nxt){
			int v = e[i].to;
			if(dis[v] < dis[u] + e[i].w){
				dis[v] = dis[u] + e[i].w;
				if(!vis[v]) q.push(v), vis[v] = true;
			}
		}
	}
}

int main()
{
	n = read(), ml = read(), md = read();
	for(int i = 1, u, v, w; i <= ml; ++i){
		u = read(), v = read(), w = read();
		add_edge(u, v, -w);
	}
	for(int i = 1, u, v, w; i <= md; ++i){
		u = read(), v = read(), w = read();
		add_edge(v, u, w);
	}
	for(int i = 1; i < n; ++i) add_edge(i + 1, i, 0);
	for(int i = n; i >= 1; --i) add_edge(0, i, 0);
	SPFA(0);
	if(flag) printf("-1\n");
	else {
		SPFA(1);
		if(dis[n] == -INF) printf("-2\n");
		else printf("%d\n", -dis[n]);
	}
	return 0;
}

写在最后

不难发现，其实有些表面上的约束条件并不能帮我们找到正确的解，表面的约束条件只是我们的一个方向和依据

我们要多去寻找题目隐含条件 以防毒瘤出题人