Main » 2013 October 24 » 好难的差分约束啊
5:02 AM 好难的差分约束啊 |
| 设num[ i ]为i时刻能够开始工作的人数，x[ i ]为实际雇佣的人数，那么x[ I ]<=num[ I ]。 设r[ i ]为i时刻至少需要工作的人数，于是有如下关系： x[ I-7 ]+x[ I-6 ]+x[ I-5 ]+x[ I-4 ]+x[ I-3 ]+x[ I-2 ]+x[ I-1 ]+x[ I ]>=r[ I ] 设s[ I ]=x[ 1 ]+x[ 2 ]…+x[ I ]，得到 0<=s[ I ]-s[ I-1 ]<=num[ I ]， 0<=I<=23 s[ I ]-s[ I-8 ]>=r[ I ]， 8<=I<=23 s[ 23 ]+s[ I ]-s[ I+16 ]>=r[ I ]， 0<=I<=7 对于以上的几组不等式，我们采用一种非常笨拙的办法处理这一系列的不等式(其实也是让零乱的式子变得更加整齐，易于处理)。首先我们要明白差分约束系统的应用对象（它通常针对多个二项相减的不等式的）于是我们将上面的所有式子都转化成两项未知项在左边，另外的常数项在右边，且中间用>=连接的式子，即: s[ I ]-s[ I-1 ]>=0 (0<=I<=23) s[ I-1 ]-s[ I ]>=-num[ I ] (0<=I<=23) s[ I ]-s[ I-8 ]>=r[ I ] (8<=I<=23) s[ I ]-s[ I+16 ]>=r[ I ]-s[ 23 ] (0<=I<= 7) 这里出现了小的困难，我们发现以上式子并不是标准的差分约束系统，因为在最后一个式子中出现了三个未知单位。但是注意到其中跟随 I变化的只有两个，于是s[23]就变得特殊起来，看来是需要我们单独处理，于是我们把 s[ 23 ]当作已知量放在右边。 经过这样的整理，整个图就很容易创建了，将所有形如 A-B>=C 的式子 我们从节点B 引出一条有向边指向 A 边的权值为C （这里注意由于左右确定，式子又是统一的>=的不等式，所以A和B是相对确定的，边是一定是指向A的） ，图就建成了 。 最后枚举所有s[ 23 ]的可能值，对于每一个s[23]，我们都进行一次常规差分约束系统问题的求解，判断这种情况是否可行，如果可行求出需要的最优值，记录到Ans中，最后的Ans的值即为所求。” |
|
|
| Total comments: 0 | |