适用问题
差分约束算法主要解决求不等式组解的问题
将数学问题建立一个图论模型利用最短路解决
首先看一组不等式方程：
给出一组包含 m 个不等式，有 n 个未知数的形如：
⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧xc1−xc1′⩽y1xc2−xc2′⩽y2⋯xcm−xcm′⩽ym
的不等式组，求任意一组满足这个不等式组的解
算法核心
上述不等式移项可得：xcm⩽xcm′+ym
类似于最短路中的三角形不等式：dist[y]⩽dist[x]+wx→y
所以我们可以转换为求解最短路的问题
由 xcm′ 引一条权为 ym 的边到 xcm
因为需要引用到单源最短路，所以我们需要建立一个超级源点
使其与每个点都连通，且与每个点的距离均设为 0
这样求出来的由超级源点到各点的最短路即为一组解
但什么时候为无解的情况 ？
即整个图中出现 负环 的情况
若存在负环，则每次松弛后都会将最短路缩短一次
最后得出来的结果就是负无穷，显然无解
算法实现
根据给出的不等式建图
任取除了 1 ~ n 的点作为超级源点，连边
由于可能存在负权边，所以使用 spfa 算法求解最短路，顺便判断负环
最后求出最短路即可
P5960 【模板】差分约束算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include<bits/stdc++.h>
using namespace std;
const int N=1e4+15;
const int inf=0x3f3f3f3f;
int n,m;
struct Edge{
int to;
int next;
int w;
}edge[N];
int cnt=1;
int head[N];
void add(int u,int v,int w){
edge[cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].w=w;
head[u]=cnt++;
}
int dist[N],vis[N],inq[N];
bool ok=true;
void spfa(int x){
memset(dist,inf,sizeof(dist));
vis[x]=1;
dist[x]=0;
inq[x]++;
queue<int> q;
q.push(x);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if(dist[v]>dist[u]+edge[i].w){
dist[v]=dist[u]+edge[i].w;
if(!vis[v]){
vis[v]=1;
inq[v]++;
q.push(v);
if(inq[v]>n){ok=false;return;}
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) add(0,i,0);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&v,&u,&w);
add(u,v,w);
}
spfa(0);
if(ok==false){printf("NO");return 0;}
for(int i=1;i<=n;i++) printf("%d ",dist[i]);
return 0;
}
|
技巧&细节
求非负解
先取最短路中的最小值，再逐一减去这个值，得到的即为非负解
1
2
3
| int minn=inf;
for(int i=1;i<=n;i++) minn=min(minn,dist[i]);
for(int i=1;i<=n;i++) printf("%d ",dist[i]-minn);
|
转换不等式
如果有 xcm−xcm′⩾ym
可以同时乘 -1 得到相反的不等式再加边
若 xcm=xcm′则等价于 xcm⩽xcm′+0 与 xcm′⩽xcm+0
