差分约束讲解
差分约束讲解
——by ysy
1.前置知识
因为差分约束是基于\(spfa\)的一种解不等式，或等式组的技巧，所以差分约束的前置知识就是\(spfa\)和对不等式的简单小变换。
2.讲解
因为差分约束只是一个技巧，所以在这里我先讲解技巧，之后再讲解例题。
建图技巧
我们将不等式组分为两种：\(A \le B+val\)以及\(A\ge B+val\)。
现在讨论第一种\(A\le B+val\)，我们在建图时\(B \rightarrow A\)建边，边权为\(val\)，所有的不等式都像这样建边的话，我们可以在建出的图上跑最短路。
现在为第二种\(A\ge B+val\)，我们在建图时\(B \rightarrow A\)建边，边权为\(val\)，所有的不等式都像这样建边的话，我们可以在建出的图上跑最长路。
如果我所有的式子给出的时候不是都为第一种或者第二种呢？如果不将式子的形式统一的话，就没法在建出来的图上单纯的跑最短路或者最长路。所以我们就需要将所有的式子的形式进行统一。
讨论完不等式了，就剩下等式。\(A=B\)我们就以这个为例。等式可以化成不等式组\(A\le B\&\& A \ge B\)。我们将这个不等式组转化成为图就是$B \rightarrow A $，边权为\(0\)，同时加另一条边\(A \rightarrow B\)，边权为\(0\)。这样一个等式就化为不等式的形式了。
我在上面写的都是大于等于或者小于等于的情况，如果是大于或者小于的情况怎么办？我在这里以大于为例：\(A\gt B \rightarrow A \ge B +1\)。我们只需要将式子化成为带等于的形式就可以了。
3.例题
1）[题目链接][https://www.lydsy.com/JudgeOnline/problem.php?id=3436]
我们看这道题目，会发现题目之中有三个限制\(X_a \ge X_b+c\)，\(X_a \le X_b+c\)，\(X_a=X_b\)。我们们根据这三个性质能建出来一个图。第一个条件就是$a \rightarrow b \(，边权为\)-c\(。第二个条件就是\)b \rightarrow a\(，边权为\)c\(。第三个条件就是\)a\rightarrow b \(和\)b\rightarrow a$边权都为\(0\)。
因为我们要判断能否成立，所以我们只需要在我们建出的图上跑最短路，并且判断是否有负环，如果有则输出\(No\)，否则输出\(Yes\)。因为要判断负环，所以我们很容易想到\(spfa\)。
#include <cstdio>#include <algorithm>using namespace std;#define N 10010#define M 10010#define inf1 1000000000#define inf2 900000000int n,m;int head[N],nxt[M<<2],to[M<<2],val[M<<2];int dis[N],idx;bool vis[N],is;void add(int a,int b,int c){nxt[++idx]=head[a],to[idx]=b,val[idx]=c,head[a]=idx;}void spfa(int p){vis[p]=true;for(int i=head[p];i;i=nxt[i]){if(dis[to[i]]<=dis[p]+val[i]) continue;dis[to[i]]=dis[p]+val[i];if(vis[to[i]]||is) {is=true;return;}spfa(to[i]);}vis[p]=false;}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int kind,a,b,c;scanf("%d",&kind);if(kind==1) scanf("%d%d%d",&a,&b,&c),c=-c;else if(kind==2) scanf("%d%d%d",&a,&b,&c),swap(a,b);else scanf("%d%d",&a,&b),c=0,add(b,a,c);add(a,b,c);}for(int i=1;i<=n;i++) dis[i]=inf1;for(int i=1;i<=n;i++) dis[i]=0,spfa(i);if(is) printf("No\n");else printf("Yes");}
我有时间的话，例题会持续更下去。这是本人的见解。有问题可以评论问我。