2020-2021:teams:farmer_john:差分约束
这是本文档旧的修订版!
差分约束系统
概念
差分约束系统是关于 $n$ 个未知量的 $m$ 个形如 $x_i-x_j\le k$ 不等式组。一般来求解的存在性问题、最优值问题以及方程组的解。
经典模型
线性约束:
一般是在一维空间里,给出一些变量,之后告诉你这些变量的大小约束关系,求某个变量的最大值/最小值
比如有$n$个人排成直线,给出之间的距离不能大于/小于某个值,求排成的最长/最短距离
设$d[i]$为第$i$个人的位置,根据大小关系建边即可。
-
区间约束
建边方法
考虑松弛过后的最短路$dis$数组,对任意一条长度为$k$从$x$到$y$的有向边,满足$ dis_y \le dis_x + k $,移项得到$ dis_y - dis_x \le k $,这与开头提到的$ x_i - x_j\le k $神似。因此我们将每个变量看成一个点,对每个不等式$ x_i - x_j\le k $连一条从$x_j$到$x_i$的长度为$k$的有向边即可,若图存在负环,意味着通过不等式相加可以得到自己小于自己,那么显然是无解的,否则一定有解,因此判负环即可。
$x_i - x_j \le k$,则连一条从$x_j$到$x_i$的长度为$k$的有向边。
$x_i - x_j \ge k$,即$x_j - x_i \le -k$,连一条从$x_i$到$x_j$的长度为$-k$的有向边。
$x_i = x_j$,等价于$x_i - x_j \le 0$且$x_i - x_j \ge 0$,连一条从$x_i$到$x_j$的长度为$0$的无向边。
最后,额外建立一个起点,向每个变量连一条权值为$0$的边,如果有解,最终$dis$数组中的取值就构成了一组可行解。
2020-2021/teams/farmer_john/差分约束.1590574567.txt.gz · 最后更改: 2020/05/27 18:16 由 jjleo