浅谈差分约束
leather_handbag
·
·
算法·理论
差分约束
约束条件 $x_i-x_j\leq c_k$ 可以变形成 $x_i\leq x_j+c_k$，这与 $dis[y]\leq dis[x]+w$ 非常相似。因此可以把每个变量 $x_i$ 看做图中的一个结点，对于每个约束条件 $x_i-x_j\leq c_k$，从结点 $j$ 向结点 $i$ 连一条长度为 $c_k$ 的有向边。
设 $dis[0]=0$ 并向每一个点连一条长为 $0$ 的边，跑最短路，若存在负环，则差分约束无解，否则，$x_i=dist[i]$ 为该差分约束的一组解．
一般用 Spfa 来做差分约束，时间复杂度 $O(nm)$。
### $\color{53C41A}\text P2294$ [[HNOI2005] 狡猾的商人](/problem/P2294)
::::info[题面]{open}
给 $m$ 个数据，每个数据 $l,r,v$ 表示 $\sum_{i=l}^r a_i=v$。
判断 $a$ 序列是否存在。
::::
本题数据范围较小，所以有多种方法。
显然，当出现 $(l,mid,v_1),(mid+1,r,v_2,),(l,r,x)$ 且 $x\ne v_1+v_2$ 时，序列不存在。
考虑差分约束建模，设 $s_i$ 为前缀和，要判断 $s_{l-1}+v=s_{r}$。
该式是等式，转化为
$$\left\{\begin{matrix}
s_{l-1}+v\le s_{r}
\\
s_{l-1}+v\ge s_{r}
\end{matrix}\right.$$
建图 $u-1 \underset{-w}{\overset w\rightleftharpoons }v$ 即可。
时间复杂度 $O(nm)$。
2. 贪心：以 $l,r$ 为第一，二关键字利用小根堆存储，对于两个相同的 $l$，则用小的把大的给抵消掉，大的变成 $(r_{min},r_{max},v_{max}-v_{min})$。时间复杂度 $O(n\log n)$。
2. 区间 DP：其实这个题里就是暴力，$dp_{i,j}=dp_{i,k}+dp_{k,j}$，如果 $dp_{i,j}$ 已经存在则判断是否相等，时间复杂度 $O(n^3)$。
3. 带权并查集：设 $cnt_i=s_{v}-s_{u-1}-v$ 表示差。
### $\color{3498DB}\text P4578 $ [[FJOI2018] 所罗门王的宝藏](/problem/P4578 )
同理，将等号限制拆成两个差分约束限制。
### $\color{3498DB}\text P5590 $ [赛车游戏](/problem/P5590 )
::::info[题面]{open}
给定图，求图所有边的边权使得从 $1$ 到 $n$ 的所有路径长度均相等且边权取值 $[1,9]$。
::::
转化为 $1\le dis_v-dis_u\le 9$。
注意判断 $1,n$ 是否联通且仅当 $u,v$ 在 $1$ 到 $n$ 的路径上时才建模，否则边权无关。
### $\color{3498DB}\text P3275 $ [糖果](/problem/P3275 )
::::info[题面]{open}
$n$ 个数，$k$ 个要求，$5$ 种情况。
1. $a=b
-
a\le b
-
a>b
-
a\ge b
-
a<b
### $\color{3498DB}\text P4926 $ [[1007] 倍杀测量者](/problem/P4926 )
::::info[题面]{open}
已知部分 $a,b$ 的值。
维护两种限制：
$$\left\{\begin{matrix}
a<b(k-T)
\\
a(k+T)< b
\end{matrix}\right.$$
找到最大的 $T$，使得条件至少有 $1$ 个不满足。
::::
一个转化：
$$\log a<\log b-\log(k-T)$$
将乘除转化成了加减，变成了差分约束性质。
对于 $a_x=c$ 的限制拆成两个约束正反建边。
注意精度问题且要建两个超级源点，一个使图联通一个维护 $a_x=c$ 的约束。
貌似精度比较水导致不用转化就能直接做？
### $\color{3498DB}\text P3530 $ [[POI 2012] FES-Festival](/problem/P3530 )
::::info[题面]{open}
给你 $m_1+m_2$ 种约束，第一种是 $a=b-1$，一种是 $a\le b$，求满足约束的数列最多有多少不同的数。
::::
考虑单个强连通分量内的数是根据单节点固定的，而不同的强连通分量可以通过整体加减来拉大距离，即不同分量实际无关联，必定可以数值完全不同，故分开考虑。
对于单个联通分量，第一种约束是固定的，发现答案是分量内最长路 $+1$，累计总和即可。
### $\color{9C3DCF}\text P3084 $ [[USACO13OPEN] Photo G](/problem/P3084 )
::::info[题面]{open}
给定 $n$ 头牛，$m$ 个区间，每个区间内**有且仅有**一头斑点牛，求一共最多有几头斑点牛。
$1\le n,m\le 2\times 10^5$。
::::
主流解法是单调队列优化 DP，也可以用差分约束做。
设 $f_i$ 表示当 $i$ 是斑点牛时，前 $i$ 头里有几头斑点牛。
约束为：
$$\left\{\begin{matrix}
0\le f_{i+1}-f_i\le 1
\\
f_b-f_{a-1}=1
\end{matrix}\right.$$
卡普通 spfa，要 LLL。
### $\color{9C3DCF}\text P2474 $ [[SCOI2008] 天平](/problem/P2474 )
::::info[题面]{open}
有 $n$ 个砝码，重量可能为 $1,2,3$，拿两个砝码 $a,b$。
已知 $k_{i,j}$：
1. $k_{i,j}=$ `=`，表示 $c_i=c_j$。
2. $k_{i,j}=$ `+`，表示 $c_i>c_j$。
3. $k_{i,j}=$ `-`，表示 $c_i<c_j$。
4. $k_{i,j}=$ `?`，表示重量关系不定。
保证 $k_{i,j}$ 合法，取 $a,b$ 放在天平左边，右边也选两个砝码放上，求：
1. 一样重的方案数。
2. 右边重的方案数。
3. 左边重的方案数。
$4\le n\le50$。$(i,j),(j,i)$ 是同一种方案。
::::
考虑约束：
1. $dis_i\ge dis_j,dis_j\ge dis_i$。
2. $dis_i\ge dis_j+1,dis_j+2\ge dis_i$。
3. $dis_j-1\ge dis_i,dis_i\ge dis_j-2$。
4. $dis_i\ge dis_j-2,dis_j+2\ge dis_i$。
计算最大可能差和最小可能差，判断天平的状态用一边的最小可能值和另一边的最大可能值判断即可。
### $\color{9C3DCF}\text P7515 $ [ [省选联考 2021 A 卷] 矩阵游戏](/problem/P7515 )
::::info[题面]{open}
有一个 $n\times m$ 的矩阵 $a_{i,j}$，$0\le a_{i,j}\le10^6$。
已知 $b_{i,j}=a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+1},1\le i<n,1\le j<m$。
求 $a_{i,j}$，无法满足输出 `No`。
$1\le n,m\le 300$。
::::
非常好的题目，很巧妙的转化。
首先设边界为 $0$，即可从右上角推出所有的 $a_{i,j}$。
并不能满足值域的限制，发现在矩阵中连续 $+x,-x$ 可以抵消 $b_{i,j}$ 的限制，考虑通过行列交替平衡 $a_{i,j}$。
$$\begin{bmatrix}
a_{1,1}+x_1-y_1 & a_{1,2}+y_2-x_1 &\cdots \\
a_{2,1}+y_1-x_2 & a_{2,2}+x_2-y_2 &\cdots \\
\vdots &\vdots &\ddots
\end{bmatrix}$$
然后对 $x_i,y_i$ 差分约束建模即可：$-a_{i,j}\le x-y\le10^6-a_{i,j}$。
注意要双端队列优化 spfa。