[SCOI2008] 天平

差分约束,套路地连边,套路地枚举得到答案

c1: \min(A-i) > \min(j-B)

c3: \min(i-A) > \min(B-j)

c2: \min(A-i)=\max(A-i) \,\, \min(B-j)=\max(B-j) \,\, A-i=B-j

具体式子看代码吧:

 

HDU 1534 Schedule Problem

考虑把几个约束关系用数学式子描述( s 为起始时间,v 为持续时间)

FAF: s_a + v_a \geqslant s_b + v_b \rightarrow s_a - s_b \geqslant v_b - v_a

FAS: s_a + v_a \geqslant s_b \rightarrow s_a - s_b \geqslant - v_a

SAF: s_a \geqslant s_b + v_b \rightarrow s_a - s_b \geqslant v_b

SAS: s_a \geqslant s_b \rightarrow s_a - s_b \geqslant 0

然后暴力建图最长路

注意判正环。

这题可以说很入门了 😉

 

POJ 1364 King

继续套路地把每个位置 a_i 拿出来当做“值”。

然后再套路地把前缀和搞出来 s_i = \sum_{j=1}^i{a_j}

然后题面的约束条件就成了:

s_r - s_{l-1} > ki

s_r - s_{l-1} < ki

差分约束用的是 \leqslant\geqslant 。 

那么就全转化成 A - B \leqslant C 算了。

那么就

s_{l-1} - s_r \leqslant -1-k

s_{r} - s_{l-1} \leqslant k-1

判负环。

 

POJ 1201 Intervals

首先复习一下差分约束系统建图基本知识:

  • 对于约束条件 a-b \leqslant c ,我们建 b \rightarrow a 的边,权为 c
  • 这个时候求图的最短路,得到的是最大解。(负环无解
  • 对于约束条件 a-b \geqslant c ,我们建 b \rightarrow a 的边,权为 c
  • 这个时候求图的最长路,得到的是最小解。(正环无解

我们来观察这个题。

尝试向差分约束去靠拢,那么观察题面,条件是

r_i - l_{i-1} \geqslant c_i

这玩意怎么来的呢? 首先我们把这个题看成“选子集”的问题(一个位置代表一个元素)

套路地,我们设 x_i 是第 i 位置的”值” ( 选中-> 1 未选中-> 0 )

套路地,我们设 s_i 是前 i 位置”值”的前缀和。

那么就可以得出以上的约束式。

并且以这样的转化,我们一定可以建立关系

0 \leqslant s_{i} - s_{i-1} \leqslant 1

这些关系已经够了。但是有个地方很不舒服,就是上面的两个 \leqslant

把式子倒过来:

s_{i} - s_{i-1} \geqslant 0

s_{i-1} - s_{i} \geqslant -1  

做完了。

注意 s_{0-1} 会爆炸所以把所有下标 +1