前言
2024.1.27 \(huge\) 在讲不要忽略算法的细节时，以最短路和差分约束为例子。发现自己差分约束忘得差不多了，于是就有了这篇博客。
负环
- 在一张图中，若存在一条边权之和为负数的回路，则称这个回路为负环。在一张图中，若存在一条边权之和为正数的回路，则称这个回路为正环。
- 如果一张图中存在负环，则可以表现为在 \(SPFA\) 的迭代过程中，无论经过多少次迭代，总存在一条有向边 \((x,y,z)\) 满足 \(dis_{s,y}>dis_{s,x}+z\) ，其中 \(s\) 为起点，从而使得 \(SPFA\) 的迭代永远不能结束。
- 代码实现
- 判定最短路径包含的边数
- 设 \(cnt_{s,x}\) 表示从起点 \(s\) 到 \(x\) 的最短路径包含的边数。规定 \(cnt_{s,s}=0\) 。当执行 \(dis_{s,y}=dis_{s,x}+z\) 时，同时更新 \(cnt_{s,y}=cnt_{s,x}+1\) 。此时如果有 \(cnt_{s,y} \ge n\) ，则说明图中存在从起点 \(s\) 出发能到达的负环。若迭代能够完成，即算法正常结束，则说明图中不存在从起点 \(s\) 出发能到达的负环。
bool spfa(int s,int n) { int i,x; memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); queue<int>q; q.push(s); dis[s]=0; vis[s]=1; while(q.empty()==0) { x=q.front(); vis[x]=0; q.pop(); for(i=head[x];i!=0;i=e[i].nxt) { if(dis[e[i].to]>dis[x]+e[i].w) { dis[e[i].to]=dis[x]+e[i].w; num[e[i].to]=num[x]+1; if(num[e[i].to]>=n) { return false;//若返回false，则说明图中有负环 } if(vis[e[i].to]==0) { q.push(e[i].to); vis[e[i].to]=1; } } } } return true;//若返回true，则说明图中没有负环 }
- 设 \(cnt_{s,x}\) 表示从起点 \(s\) 到 \(x\) 的最短路径包含的边数。规定 \(cnt_{s,s}=0\) 。当执行 \(dis_{s,y}=dis_{s,x}+z\) 时，同时更新 \(cnt_{s,y}=cnt_{s,x}+1\) 。此时如果有 \(cnt_{s,y} \ge n\) ，则说明图中存在从起点 \(s\) 出发能到达的负环。若迭代能够完成，即算法正常结束，则说明图中不存在从起点 \(s\) 出发能到达的负环。
- 卡时做法
- 对于上面的判定最短路径包含的边数做法，可以根据运行时间限制，给 \(cnt_{y}\) 设定一个上界，超出时直接判定存在负环。
......//剩余代码同上 if(num[e[i].to]>=MAX_N)//MAX_N为设定的上界 { return false;//若返回false，则说明图中有负环 } ......//剩余代码同上
- 对于上面的判定最短路径包含的边数做法，可以根据运行时间限制，给 \(cnt_{y}\) 设定一个上界，超出时直接判定存在负环。
- 将 \(SPFA\) 从基于 \(BFS\) 实现改为基于 \(DFS\) 实现
- 判定最短路径包含的边数
- 例题
差分约束
- 差分约束系统是由 \(m\) 个 \(n\) 元一次不等式组成的 \(n\) 元一次不等式组，形如 \(\begin{cases}x_{a_{1}}-x_{b_{1}} \le c_{1}\\x_{a_{2}}-x_{b_{2}} \le c_{2} \\ \dots \\ x_{a_{m}}-x_{b_{m}} \le c_{m}\end{cases}\) ，其中对于每一个 \(i(1 \le i \le n)\) 均有 \(1 \le a_{i},b_{i} \le n\) 。我们要解决的问题是：求一组解 \(\begin{cases}x_{1}=ans_{1} \\ x_{2}=ans_{2} \\ \dots \\ x_{n}=ans_{n}\end{cases}\) ，使得所有的不等式均成立或给出无解信息。
- 代码实现
- 对于第 \(i(1 \le i \le m)\) 个不等式 \(x_{a_{i}}-x_{b_{i}} \le c_{i}\) ，可以变形为 \(x_{a_{i}} \le x_{b_{i}}+c_{i}\) 。这与三角形不等式 \(dis_{s,y} \le dis_{s,x}+z\) 十分相似。因此我们可以把变量 \(x_{a_{i}}\) 看做有向图中的一个节点 \(a_{i}\) ，从节点 \(b_{i}\) 向节点 \(a_{i}\) 连一条 \(c_{i}\) 的有向边。
- 由不等式基本性质，容易有若 \(\begin{cases}x_{1}=ans_{1} \\ x_{2}=ans_{2} \\ \dots \\ x_{n}=ans_{n}\end{cases}\) 是原差分约束系统的一组解，则 \(\begin{cases}x_{1}=ans_{1}+d \\ x_{2}=ans_{2}+d \\ \dots \\ x_{n}=ans_{n}+d\end{cases}\) 也是原差分约束系统的一组解，其中 \(d\) 为常数。
- 如果题目要求求非负整数解或通过如上的构图方式所构出的图不连通时，需要加入一个超级源点 \(0\) ，并令 \(x_{0}=0\) ，同时原差分约束系统增加了 \(n\) 个 \(n\) 元一次不等式 \(x_{a_{i}}-x_{0} \le 0\) 。
- 设 \(dis_{0,0}=0\) ，以 \(0\) 为起点求单源最短路。若图中存在负环，则给定的差分约束系统无解；否则， \(\begin{cases}x_{1}=dis_{1} \\ x_{2}=dis_{2} \\ \dots \\ x_{n}=dis_{n}\end{cases}\) 为原差分约束系统的一组解。
- 另外，若对于任意一个 \(i\) 有 \(x_{a_{i}}-x_{b_{i}} \ge c_{i}\) 可以从节点 \(b_{i}\) 向节点 \(a_{i}\) 连一条 \(c_{i}\) 的有向边，求单源最长路，判定有无解变为是否存在正环；或者可以转化为 \(x_{b_{i}}-x_{a_{i}} \le -c_{i}\) ，然后按照上面的算法求解。
- 同样地，若对于任意一个 \(i\) 有 \(x_{a_{i}}-x_{b_{i}} \le c_{i}\) 也可以转化为 \(x_{b_{i}}-x_{a_{i}} \ge -c_{i}\) 。
- 另外，若对于任意一个 \(i\) 有 \(x_{a_{i}}-x_{b_{i}} \ge c_{i}\) 可以从节点 \(b_{i}\) 向节点 \(a_{i}\) 连一条 \(c_{i}\) 的有向边，求单源最长路，判定有无解变为是否存在正环；或者可以转化为 \(x_{b_{i}}-x_{a_{i}} \le -c_{i}\) ，然后按照上面的算法求解。
- 对于第 \(i(1 \le i \le m)\) 个不等式 \(x_{a_{i}}-x_{b_{i}} \le c_{i}\) ，可以变形为 \(x_{a_{i}} \le x_{b_{i}}+c_{i}\) 。这与三角形不等式 \(dis_{s,y} \le dis_{s,x}+z\) 十分相似。因此我们可以把变量 \(x_{a_{i}}\) 看做有向图中的一个节点 \(a_{i}\) ，从节点 \(b_{i}\) 向节点 \(a_{i}\) 连一条 \(c_{i}\) 的有向边。
- 例题
- luogu P5960 【模板】差分约束
void spfa(ll s,ll n)//单源最短路找负环 { ll i,x; memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); queue<ll>q; q.push(s); dis[s]=0; vis[s]=1; while(q.empty()==0) { x=q.front(); for(i=head[x];i!=0;i=e[i].nxt) { if(dis[e[i].to]>dis[x]+e[i].w) { dis[e[i].to]=dis[x]+e[i].w; num[e[i].to]=num[x]+1; if(num[e[i].to]>=n+1) { cout<<"NO"<<endl; exit(0); } if(vis[e[i].to]==0) { q.push(e[i].to); vis[e[i].to]=1; } } } vis[x]=0; q.pop(); } } int main() { ll n,m,u,v,w,i; cin>>n>>m; for(i=1;i<=n;i++) { add(0,i,0); } for(i=1;i<=m;i++) { cin>>u>>v>>w; add(v,u,w); } spfa(0,n); for(i=1;i<=n;i++) { cout<<dis[i]<<" "; } return 0; }void spfa(ll s,ll n)//单源最长路找正环 { ll i,x; memset(vis,0,sizeof(vis)); memset(dis,-0x3f,sizeof(dis)); queue<ll>q; q.push(s); dis[s]=0; vis[s]=1; while(q.empty()==0) { x=q.front(); for(i=head[x];i!=0;i=e[i].nxt) { if(dis[e[i].to]<dis[x]+e[i].w) { dis[e[i].to]=dis[x]+e[i].w; num[e[i].to]=num[x]+1; if(num[e[i].to]>=n+1) { cout<<"NO"<<endl; exit(0); } if(vis[e[i].to]==0) { q.push(e[i].to); vis[e[i].to]=1; } } } vis[x]=0; q.pop(); } } int main() { ll n,m,u,v,w,i; cin>>n>>m; for(i=1;i<=n;i++) { add(0,i,0); } for(i=1;i<=m;i++) { cin>>u>>v>>w; add(u,v,-w); } spfa(0,n); for(i=1;i<=n;i++) { cout<<dis[i]<<" "; } return 0; }- 以上两种不同的写法均可。
- 以下题目均使用单源最长路找正环求解。
- 以上两种不同的写法均可。
- luogu P1260 工程规划
- tgHZOJ 183. 小K的农场
- 数据弱化版：BZOJ 3436.小K的农场 | luogu P1993 小 K 的农场
- 本题因数据经过特殊的构造，卡掉了基于 \(BFS\) 实现的 \(SPFA\) 。故需要使用
deque优化 \(SPFA\) 或使用 \(DFS\) 式的 \(SPFA\)。但是因为数据较水，使用卡时做法也可通过。
- luogu P3275 [SCOI2011] 糖果
- luogu P4878 [USACO05DEC] Layout G
- SP116 INTERVAL - Intervals
- LibreOJ 10088. 「一本通 3.4 例 2」出纳员问题
- luogu P5960 【模板】差分约束
参考资料
《算法竞赛进阶指南》——李煜东
标签：le,luogu,笔记,约束,负环,vis,差分,dis From： https://www.cnblogs.com/The-Shadow-Dragon/p/17991944