差分约束

差分约束，一般用来解决有\(n\)个未知数，\(m\)个不等式方程的问题，形如：

\[\begin{cases}
\ x_{a_1}-x_{b_1}\leq y_1\\
\ x_{a_2}-x_{b_2}\leq y_2\\
\ \cdots\\
\ x_{a_m}-x_{b_m}\leq y_m\\
\end{cases}
\]

可以判断有没有解，以及给出一组解

简单观察可以知道，每个未知数的系数都为\(1\)，且不等式一边是两个未知数相减，另一边是一个常数

为了达到这种形式，一般都需要将题目中的关系进行变形

模板题：P5960 【模板】差分约束算法

如何求解

考虑对于每个不等式\(x_i-x_j\leq y\)，可以变形成\(x_i\leq x_j+y\)

这个式子，可以容易联想到最短路算法中的不等式\(dis(v)\leq dis(u)+w\)，（容易吗？

那么，可以用最短路的方法来求解，从\(j\)向\(i\)联一条边权为\(y\)的边（\(i\)对应终点\(v\)）

然后，就要新建一个虚拟节点\(n+1\)，从它向每个节点连一个权值为\(0\)的边，\(dis(i)\leq dis(n+1)+0\)

求出的各项\(dis(i)\)其实就是对应的\(x_i\)

又由于\(dis(n+1)=0\)，所以此时的\(dis(i)\)均小于\(0\)，那么我们求出来的这组解，就是所有小于\(0\)的解里，最大的一组

那么如果产生了负环，就会出现\(x<x\)的情况，然后肯定无解，证明应该不难，但不想证了

因为在一个没有负环的图上，最短路肯定不会经过多于\(n\)个点，也不会经过多于\(n-1\)条边

所以，我们用 spfa 来求解这个最短路问题，如果某个节点入队\(n\)次，就说明存在负环

还有一种，就是记录\(cnt_i\)为\(1\rightarrow i\)的最短路上的点的个数，如果\(cnt_i>n\)就说明存在负环

这种方法倒是更直观，据说跑起来也更快

当然，\(cnt_1=1,cnt_v=cnt_u+1\)

但是代码里放的是第一种

没错，spfa 肯定没死，他是唯一能处理负环的算法（起码我没听说过其它的

最短路

所以可以写出用最短路实现的代码：

#include<cstdio>

#include<queue>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<iomanip>

#include<cstring>

#define reg register

#define EN std::puts("")

#define LL long long

inline int read(){

	int x=0,y=1;

	char c=std::getchar();

	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}

	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}

	return y?x:-x;

}

int n,m;

int fir[5006],nex[10006],to[10006],w[10006],tot;

int cnt[5005],in[5005];

int dis[5005];

std::queue<int>q;

inline void add(int a,int b,int c){

	to[++tot]=b;w[tot]=c;

	nex[tot]=fir[a];fir[a]=tot;

}

inline int spfa(){

	q.push(n+1);

	std::memset(dis,0x3f,sizeof dis);

	dis[n+1]=0;in[n+1]=1;

	while(!q.empty()){

		reg int u=q.front();q.pop();in[u]=0;

		for(reg int v,i=fir[u];i;i=nex[i]){

			v=to[i];

			if(dis[v]>dis[u]+w[i]){

				dis[v]=dis[u]+w[i];

				if(!in[v]){

					if(++cnt[v]==n) return 0;

					in[v]=1;q.push(v);

				}

			}

		}

	}

	return std::rand();

}

int main(){

	n=read();m=read();

	for(reg int i=1;i<=n;i++) add(n+1,i,0);

	for(reg int a,b,c,i=1;i<=m;i++){

		a=read();b=read();c=read();

		add(b,a,c);

	}

	if(!spfa()) std::puts("NO");

	else for(reg int i=1;i<=n;i++) std::printf("%d\n",dis[i]);

	return 0;

}

最长路

其实不等式\(x_i-x_j\leq y\)还可以变形成\(x_j\geq x_i-y\)

所以就应该从\(i\)向\(j\)连一个权值为\(-y\)的边，然后跑最长路，判断正环

当然，虚拟节点也要建，从\(n+1\)连向\(i\)，代表\(dis(i)\geq dis(n+1),dis(n+1)=0\)

因此，这种方法求出的是，当\(x_i\geq 0\)，的最小解

所以代码是这样的：

#include<cstdio>

#include<queue>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<iomanip>

#include<cstring>

#define reg register

#define EN std::puts("")

#define LL long long

inline int read(){

	int x=0,y=1;

	char c=std::getchar();

	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}

	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}

	return y?x:-x;

}

int n,m;

int fir[5006],nex[10006],to[10006],w[10006],tot;

int cnt[5005],in[5005];

int dis[5005];

std::queue<int>q;

inline void add(int a,int b,int c){

	to[++tot]=b;w[tot]=c;

	nex[tot]=fir[a];fir[a]=tot;

}

inline int spfa(){

	q.push(n+1);

	for(reg int i=1;i<=n;i++) dis[i]=-5e8;

	in[n+1]=1;

	while(!q.empty()){

		reg int u=q.front();q.pop();in[u]=0;

		for(reg int v,i=fir[u];i;i=nex[i]){

			v=to[i];

			if(dis[v]<dis[u]+w[i]){

				dis[v]=dis[u]+w[i];

				if(!in[v]){

					if(++cnt[v]==n) return 0;

					in[v]=1;q.push(v);

				}

			}

		}

	}

	return std::rand();

}

int main(){

	n=read();m=read();

	for(reg int i=1;i<=n;i++) add(n+1,i,0);

	for(reg int a,b,c,i=1;i<=m;i++){

		a=read();b=read();c=read();

		add(a,b,-c);

	}

	if(!spfa()) std::puts("NO");

	else for(reg int i=1;i<=n;i++) std::printf("%d\n",dis[i]);

	return 0;

}

一些题目

在处理差分约束题目时，主要就是要把关系进行变形

看清楚边是\(i\rightarrow j\)还是\(j\rightarrow i\)，边权是\(y\)还是\(-y\)

如果出现未知数系数不为\(1\)的情况，一般使用乘积最短路的形式，但这时候就要求没有常数，也就是\(x_i\leq kx_j\)

P1993 小K的农场，题解，比较经典的一题

P4926 [1007]倍杀测量者，这个就是刚才说的乘积最短路，但是具体的实现是要取\(\log\)，然后变成加法的，洛谷上有一个名为“最短路”的题就是这个

SCOI2011 糖果

 虫洞，uva上的一题

巴特西

P5960 差分约束算法模板

差分约束

如何求解

最短路

最长路

一些题目

最新文章

热门文章