差分约束系统

差分约束系统是关于 $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$的有向边即可。若图存在负环，意味着通过不等式相加可以得到自己小于自己，那么显然是无解的；否则既然这个图不存在负环，那么我们通过最短路算法一定可以松弛所有点使得$dis$数组满足我们附加的条件，因此一定有解。
• $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$数组中的取值就构成了一组可行解。

传送门

• 题意：$n$个重量范围已知的砝码，部分轻重关系已知，先在天平左侧放两个砝码，求任选两个砝码使天平向左倾/水平/向右倾的方案数
• 题解：
  • 由于只知道轻重关系，考虑用$dmax[i][j]$记录$i-j$的最大值，最小值同理。
  • 建出来之后不难发现，和$floyd$求最短路有点像欸
  • 于是用$floyd$跑一遍确定一下上下界，然后枚举两个砝码就行了

传送门

• 题意：有 $n+m$ 个变量，给定 $k$ 组限制，每次告诉你 $x_r+y_c=k$，问是否有可行解。
• 题解：将 $x_r+y_c=k$ 转变为两个不等式 $x_r-(-y_c)\le k,x_r-(-y_c)\ge k$ 建边判负环即可。

传送门

• 题意：已知某些位置的 $S_i$ ,求最大的 $T$ 使得存在一个序列 $S$ 满足 $m$ 个形如 $S_a>S_b\times (k_i-T),S_a>S_b\times \frac{1}{k_j+T}$ 的限制。如果不存在则输出 $-1$。序列长度 $n\le 1000$，限制个数 $m\le 1000$
• 题解：将限制取对数，然后对于 $T$ 二分。建图的时候要将已经确定的 $S_i$ 可以建立两个形如 $S_0-S_i\le -S_i,S_i-S_0\le S_i$ 的限制即可，然后就可以判断是否有解。

传送门

• 题意：给定 $m (m\le 1000)$ 个限定，每个限定为 $\sum_{i=s}^t a_i=v_j$，问是否存在这样一个序列 $a$。 序列长度 $n\le 100$
• 题解：考虑前缀和 $sum_i=\sum_{j=1}^i a_j$ ，限定转化为 $sum_t-sum_{s-1}=v_j$ ，将等式转化为两个不等式 $sum_t-sum_{s-1}\ge v_j,sum_t-sum_{s-1}\le v_j$ 即可。