差分约束

定义

差分约束是一种特殊的一元不等式组，其中每一项都形如\(x_{i}-x_{j}\le m_{k}\)，其中\(m_{k}\)是常数。
差分约束算法可以求出一组可行解。

推理

我们注意到，每一个不等式都可以变形成\(x_{i}\le x_{j}+m_{k}\)
同时对于一个图的最短路\(dist[]\)，一定有\(dist(y)<=dist(x)+val(x,y)\)
我们发现这两个式子的形式极为相似，于是考虑转化。
我们将\(x_{i}\)与\(x_{j}\)视为节点，\(m_{k}\)视为边权，从\(x_{j}\)向\(x_{i}\)连一条权值为\(m_{k}\)的有向边。

过程

设立\(0\)号节点，向所有节点连一条\(0\)边，然后从\(0\)开始跑单源最短路。
如果图中存在负环，则无解；否则\(x_{i}=dist[i]\)是一组可行解。

扩展

\(x_{i}-x_{j}\ge m_{k}\Leftrightarrow x_{j}-x_{i}\le -m_{k}\Leftrightarrow add(i,j,-m_{k})\)
\(x_{i}=x_{j}\Leftrightarrow x_{i}-x_{j}\ge 0,x_{i}-x_{j}\le 0\Leftrightarrow add(i,j,0),add(j,i,0)\)
\(\frac{x_{i}}{x_{j}}\le m_{k}\Leftrightarrow \log_{2}x_{i}-\log_{2}x_{j}\le m_{k}\Leftrightarrow add(j,i,\log_{2}m_{k})\)

题目

P5960 【模板】差分约束算法 模板题