2020-2021:teams:farmer_john:差分约束
这是本文档旧的修订版!
差分约束系统
概念
差分约束系统是关于 $n$ 个未知量的 $m$ 个形如 $x_i-x_j\le k$ 不等式组。一般来求解的存在性问题、最优值问题以及方程组的解。
经典模型
线性约束:
一般是在一维空间里,给出一些变量,之后告诉你这些变量的大小约束关系,求某个变量的最大值/最小值
比如有$n$个人排成直线,给出之间的距离不能大于/小于某个值,求排成的最长/最短距离
设$d[i]$为第$i$个人的位置,根据大小关系建边即可。
-
区间约束
建边方法
2020-2021/teams/farmer_john/差分约束.1590573852.txt.gz · 最后更改: 2020/05/27 18:04 由 jjleo