负环与差分约束系统 学习笔记

## 负环 在一张带权图 $G$ 中，若有一个环满足**环上边权之和为负**，则称这个环为**负环**。 可以发现，带负环的图不存在最短路，因为可以构造一条路径不停地绕着这个环走使总长度为 $-\infty$。 一般可以用 Bellman-Ford 或 SPFA 判负环，其中 SPFA 在随机图上表现出色，但二者的最劣时间复杂度都是 $\Theta(nm)$ 的。 - [P3385 【模板】负环](https://www.luogu.com.cn/problem/P3385) 我们发现，应用 Bellman-Ford 算法时，负环不存在时 $1$ 号点到任意点的最短路包含的边数不超过 $n-1$（否则肯定会重复经过某个点）。 因此可以在做完 $n-1$ 轮松弛后再遍历一遍所有边，若依然能松弛则表示有负环存在。 核心代码： ```c++ int n,m,dis[N]; bool vis[N]; struct edge { int u,v,w; } e[M]; int tot; void solve() { cin>>n>>m; tot=0; fo(i,1,m) { tot++, scanf("%d%d%d",&e[tot].u,&e[tot].v,&e[tot].w); if(e[tot].w>=0) { tot++, e[tot].u=e[tot-1].v; e[tot].v=e[tot-1].u, e[tot].w=e[tot-1].w; } } memset(dis,0x3f,sizeof(dis)), memset(vis,0,sizeof(vis)); dis[1]=0, vis[1]=true; fo(i,2,n) { bool ok=true; fo(j,1,tot) if(dis[e[j].v]>dis[e[j].u]+e[j].w) { ok=false, dis[e[j].v]=dis[e[j].u]+e[j].w; if(vis[e[j].u]) vis[e[j].v]=true; } if(ok) break; } fo(j,1,tot) if(vis[e[j].u]&&vis[e[j].v]&&dis[e[j].v]>dis[e[j].u]+e[j].w) return puts("YES"), void(); puts("NO"); } ``` 对应到 SPFA 算法上，则需要判断一个点入队次数是否 $\geq n$，若 $\geq n$ 则表示有负环存在。 还有一种方法是记录每个点的最短路长度，这种方法一般效率更高。 ## 差分约束系统 ### 概念 **差分约束系统（system of difference constraints）**是一种特殊的 $n$ 元一次不等式组，里面的每一个条件都是 $$ x_i-x_j \le c_k $$ 的形式，也就是**两变量之差不大于某数**。（若要求不小于可以把 $i,j$ 调换顺序） 问题要求给出一组合法解，或者判断它无解。 ### 模型的转换 可以移项得到： $$ x_i\le x_j+c_k $$ 这正是最短路中的**三角形不等式**的形式： $$ \forall (u,v,w)\in E,\ dis_v\le dis_u+w $$ 那么我们可以尝试建图，对每个不等式连边 $(j,i,c_k)$，然后考虑跑最短路。 但是这个图不一定是一个流图，我们难以找出一个源点跑单源最短路，于是我们可以新建一个虚拟源点 $0$，对每个 $i\in[1,n]$ 连边 $(0,i,0)$。 现在我们以 $0$ 号点为源点跑一个单源最短路，跑出来每个点的最短路 $dis_i$ 一定是一组合法的解。 那么无解的情况呢？我们发现，差分约束系统无解当且仅当建出的图中不存在最短路，也即图中有负环。 这样我们就能以 $\mathcal O(n+m)$ 的时间解决这一问题了。 差分约束系统有一个平凡的性质： > 若 $\{x_1,x_2,\cdots,x_n\}$ 是差分约束系统的一组合法解，则 $\forall \Delta\in\mathbb R$，$\{x_1+\Delta,x_2+\Delta,\cdots,x_n+\Delta\}$ 也是一组合法解。 这个结论是显然的。若 $x_i$ 中有负数，使用中常取 $\Delta=-\min{x_i}$，可构造出一组非负解。 - [P5960 【模板】差分约束算法](https://www.luogu.com.cn/problem/P5960) 这里使用 SPFA 算法求最短路。 ```c++ #include<bits/stdc++.h> using namespace std; #define fo(v,a,b) for(int v=a;v<=b;v++) #define fr(v,a,b) for(int v=a;v>=b;v--) #define il inline const int N=5010, M=20010; int n,m; int head[N], Next[M], ver[M], edge[M], tot; void add_edge(int x,int y,int z) { ver[++tot]=y, edge[tot]=z; Next[tot]=head[x], head[x]=tot; } int dis[N], cnt[N]; bool vis[N]; queue<int> q; int main() { cin>>n>>m; fo(i,1,m) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add_edge(y,x,z); } fo(i,1,n) add_edge(0,i,0); memset(dis,0x3f,sizeof(dis)); dis[0]=0, vis[0]=true, q.push(0); while(q.size()) { int x=q.front(); q.pop(); vis[x]=false; for(int i=head[x]; i; i=Next[i]) { int y=ver[i]; if(dis[y]>dis[x]+edge[i]) { dis[y]=dis[x]+edge[i]; cnt[y]=cnt[x]+1; if(cnt[y]>=n+1) return puts("NO"),0; if(!vis[y]) vis[y]=true, q.push(y); } } } fo(i,1,n) printf("%d ",dis[i]); return 0; } ``` 注意因为实际上有 $n+1$ 个点，所以里面判负环需要写成 $\geq n+1$。 还有注意存边的数组不要开小！！！ ## 常见建模思路 主要难在建模...... 而且有些差分约束的题目还可以用贪心做，因此大多数差分约束的题目第一眼看是贪心（ 总之就是看着十分难搞的**二元约束性**问题都可以考虑差分约束，最主要的点还是**二元**吧。 ### Trick 1 - 等号化为不等号 **例题：**[P4578 [FJOI2018]所罗门王的宝藏](https://www.luogu.com.cn/problem/P4578) 我们设 $row_i$ 为第 $i$ 行的转动结果，$col_i$ 为第 $i$ 列的转动结果。那么对于每个限制 $(x,y,c)$ 有： $$ row_i+col_i=c $$ 好像不太好搞？实际上，原式就是： $$ row_i-(-col_i)=c $$ **（重点）既然有差分约束的影子了，那么就可以把这个等号拆成两个约束：** $$ \begin{cases} row_i-(-col_i)\le c \\ (-col_i)-row_i\le -c \end{cases} $$ 也就是说**等号相当于连反向、反权边**。 [Code](https://www.luogu.com.cn/record/59411044) ### Trick 2 - 前缀和形式 **例题：**[P2294 [HNOI2005]狡猾的商人](https://www.luogu.com.cn/problem/P2294) 这个前缀和的提示还算比较明显的，有些题目可能更为隐晦。 一般题目给出的约束是**区间上一整段 至少/至多 的价值**，就可以考虑前缀和形式。 设 $S_i=\sum_{k=1}^i a_i$，那么每个限制条件 $(s,t,v)$ 可被写作： $$ S_t-S_{s-1}\le v $$ $$ S_{s-1}-S_t\le -v $$ 然后就可以搞了。注意这里 $s-1$ 能取到 $0$，因此可以把源点设成 $n+1$。 [Code](https://www.luogu.com.cn/record/59413480) ### Trick 3 - 结合最短路和最长路 **例题：**[P2474 [SCOI2008]天平](https://www.luogu.com.cn/problem/P2474)（难） 考虑到里面要求**必定成立**，因此我们考虑跑出每个组差的上界和下界。 我们注意到对于任意 $x,y$，由于 $a_x,a_y\in[1,3]$，因此 $-2\le a_x-a_y\le2$，这便是所有字符需要满足的条件。 `+`：$a_x>a_y\Rightarrow a_x-a_y\geq 1$，有 $a_x\geq a_y+1$。 `-`：$a_x<a_y\Rightarrow a_x-a_y\le -1$，有 $a_x\leq a_y-1$。 `=`：$a_x=a_y\Rightarrow a_x\le a_y\land a_y\le a_x$。 `?`：$a_x\geq a_y-2\land a_x\le a_y+2$。 因此我们注意到**对同一个 $a_x$，既有 $\le$ 的限制条件，又有 $\ge$ 的限制条件**。 这里如果简单地取负数来把不等号反向，会多出来一个变量 $-a_x$，而它与 $a_x$ 是绑定死的，难以作为一个新变量。 这时我们可以考虑**同时求最短路、最长路**来把问题转化成类似于差分约束的形式。 建图部分： ```c++ fo(i,1,n) fo(j,1,n) dis0[i][j]=dis1[i][j]=114514; fo(i,1,n) { scanf("%s",s+1); fo(j,1,n) { if(s[j]=='+') { dis0[i][j]=1, dis1[i][j]=2, dis0[j][i]=-2, dis1[j][i]=-1; } else if(s[j]=='-') { dis0[i][j]=-2, dis1[i][j]=-1, dis0[j][i]=1, dis1[j][i]=2; } else if(s[j]=='=') { dis0[i][j]=dis1[i][j]=dis0[j][i]=dis1[j][i]=0; } else if(dis0[j][i]==114514) { dis0[j][i]=-2, dis1[j][i]=2; } } } ``` 由于要求出每个点对的差值，因此跑一个 Floyd 求出最短路和最长路，暴力枚举统计答案。 （这里的 $\texttt{dis0[i][j]}$ 表示 $x_i-x_j$ 的最小值， $\texttt{dis1[i][j]}$ 表示 $x_i-x_j$ 的最大值） 注意这里只考虑 $\texttt{dis0[A][i],dis1[j][B]}$ 是不行的，因为一边算出的信息不一定全。 ```c++ fo(i,1,n) if(i!=A&&i!=B) fo(j,i+1,n) if(j!=A&&j!=B) { if( dis0[A][i]>dis1[j][B] || dis0[A][j]>dis1[i][B] ) cnt1++; else if( (dis0[A][i]==dis1[j][B]&&dis1[A][i]==dis0[j][B]) || (dis0[A][j]==dis1[i][B]&&dis1[A][j]==dis0[i][B]) ) cnt2++; else if( dis1[A][i]<dis0[j][B] || dis1[A][j]<dis0[i][B] ) cnt3++; } ``` [Code](https://www.luogu.com.cn/record/59494073) 总结：用最短路径求差分方程组的最大解，用最长路径求差分方程组的最小解。 ### Trick 4 - 用 Tarjan 代替 Bellman-Ford/SPFA 这个东西真的很难想到（ **例题：**[P3275 [SCOI2011]糖果](https://www.luogu.com.cn/problem/P3275) 一眼差分约束，然后发现 $n$ 是 $10^5$ 级别的，很慌，可能会卡 SPFA。 注意到这里的差值**只有 $1$**，因此可以考虑先用 Tarjan 缩点然后在 DAG 上 DP。 具体看代码。[Code](https://www.luogu.com.cn/record/59507124) ### Trick 5 - 取 $\log$ 来化乘为加 - [P4926 [1007]倍杀测量者](https://www.luogu.com.cn/problem/P4926) 显然先上一个二分答案，二分完自然想到从反面（没有任何人女装）的情况入手。 列出不等式组跑最短路，若无解则说明有人女装，否则无人女装。 但是，列出的不等式是这样的： $$ d_u\geq kd_v $$ 这个不等式**含有倍数**。 怎么处理？我们发现**可以通过 $\log$ 使运算降级**，因此： $$ \ln d_u\geq\ln d_v+\ln k $$ 这样就可以了。[Code](https://www.luogu.com.cn/record/59610624) --- 由于做法实在多变，就不放了qwq