用户工具

站点工具


2020-2021:teams:farmer_john:差分约束

这是本文档旧的修订版!


差分约束系统

概念

差分约束系统是关于 $n$ 个未知量的 $m$ 个形如 $x_i-x_j\le k$ 不等式组。一般来求解的存在性问题、最优值问题以及方程组的解。

经典模型

  • 线性约束:
    • 一般是在一维空间里,给出一些变量,之后告诉你这些变量的大小约束关系,求某个变量的最大值/最小值
    • 比如有$n$个人排成直线,给出之间的距离不能大于/小于某个值,求排成的最长/最短距离
    • 设$d[i]$为第$i$个人的位置,根据大小关系建边即可。
    • 两道例题:HDU3592[SCOI2011]糖果
  • 区间约束
    • 相比于上一个模型,我们处理的对象变成了区间。
    • 从例题POJ 1201来理解这个模型,给定$n$个区间,在数轴上选择最少的点,使得第$i$个区间至少有$c_i$个点。
    • 参考前缀和的思想,我们可以用$d[i]$代表$[0,i]$的区间里选点的数量,则对于区间$[a_i,b_i]$,其中点的数量为$d[b_i]-d[a_i-1]$,联立$c_i$建图。同时注意为了保证$d[i]$合法,还要有$0\leq d[i+1]-d[i]\leq 1$。
    • 另一道例题:POJ 1716

建边方法

  • 考虑松弛过后的最短路$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