环球精选！差分约束学习笔记

【资料图】

2023.5.6 写的太烂了重新写

差分约束系统是一种特殊的 \(n\) 元一次不等式组，它包含 \(n\) 个变量 \(x_{1},x_{2},...,x_{n}\) 以及 \(m\) 个约束条件，每一个约束条件都是两个其中的变量做差构成的，形如 \(x_{i}-x_{j}\le c_{k}\)，其中 \(1\le i,j\le n,i\ne j,1\le k\le m\) 并且 \(c_{k}\) 是常数（可以为正数或非正数）。------- OI Wiki

通俗一点讲，这类问题都是给定 \(n\) 个变量，\(m\) 个限制，类似于：

有了这些条件，一般的题目会让你求出一组合法的解，也就是求这 \(n\) 个变量的合法的值。

我们可以建一个超级源点，然后向每一个点连一条边权为 \(0\) 的边，然后跑单源最短路；而上面的 \(m\) 个限制都可以变形为 \(x_{i}\le x_{j}+c_{k}\)，这个东西很容易想到我们在跑最短路的时候的松弛操作里的 \(dis[v]\le dis[u]+w\)，因此我们就可以把每一个变量看作是一个图中的点，对于每一个条件 \(x_{i}-x_{j}\le c_{k}\)，从 \(j\) 向 \(i\) 连一条边权为 \(c_{k}\) 的有向边。

我们在求解的时候一般用 SPFA 来跑，虽然他最坏的时间复杂度是 \(O(nm)\) 的，但是我们的差分约束里面要是有负环的话，就说明是无解，再加上有负边权，SPFA 这个已死的算法成了最好的方法，更何况他在一些随机的图中跑的飞快。

最后一个问题，最后转化的式子是 \(x_{i}\le x_{j}+c_{k}\)，为什么跑最短路？

但是我觉得，当你建图的时候使用的是 \(x_{i}-x_{j}\le c_{k}\) 形式的方程组建图时，即 \(j\) 向 \(i\) 连一条权值为 \(c_{k}\) 的边，应该选择跑最短路。

如果使用的是 \(x_{i}-s_{j}\ge c_{k}\) 形式的方程组来建图时，应该选择跑最长路。

code:

#include#define INF 0x3f3f3f3f#define N 50100using namespace std;int n,m,cnt,head[N];queueq;struct SB{int w,v,next;}e[N<<1];int dis[N],tot[N],vis[N];inline void add(int u,int v,int w){e[++cnt].v=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;}int SPFA(){q.push(0);vis[0]=1;tot[0]++;while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];i;i=e[i].next){int v=e[i].v,w=e[i].w;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;q.push(v);vis[v]=1;tot[v]++;if(tot[v]==n+1)return 0;}}}return 1;}int main(){cin>>n>>m;for(int i=1;i<=n;i++)  dis[i]=INF;for(int i=1;i<=n;i++)  add(0,i,0);for(int i=1;i<=m;i++){int x,y,z;cin>>x>>y>>z;add(y,x,z);}if(!SPFA())  cout<<"NO"<