Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:因为枚举时替代掉的方程组不等价

Posted by llyanwenyuan at 2012-04-07 21:19:52 on Problem 1275
In Reply To:因为枚举时替代掉的方程组不等价 Posted by:aoxboxcox at 2011-04-20 15:54:05
> 详细解释一下。
> 为避免负数,时间计数1~24。令:
> R[i] i时间需要的人数 (1<=i<=24)
> T[i] i时间应聘的人数 (1<=i<=24)
> x[i] i时间录用的人数 (0<=i<=24),其中令x[0]=0
> 再设s[i]=x[0]+x[1]+……+x[i] (0<=i<=24),
> 由题意,可得如下方程组:
> (1) s[i]-s[i-8]>=R[i]        (8<=i<=24)
> (2) s[i]-s[16+i]>=R[i]-s[24] (1<=i<=7)
> (3) s[i]-s[i-1]>=0           (1<=i<=24)
> (4) s[i-1]-s[i]>=-T[i]       (1<=i<=24)
> 
> 这个差分约束有个特殊的地方,(2)的右边有未知数s[24]。
> 这时可以通过枚举s[24]=ans来判断是否有可行解。
> 即(2)变形为(2') s[i]-s[16+i]>=R[i]-ans (1<=i<=7)
> 再通过SPFA求解(1)(2')(3)(4)。
> 
> 不过最后有可能出现这种情况:
> (1)(2')(3)(4)虽然有解,但求出的s[24]小于代入(2')里的ans!
> 这时,显然得到的s[]不满足原来的(2)了(请仔细比较(2)与(2'))。
> 不过虽然得到的解不满足原方程组,但这并不代表(1)(2)(3)(4)在s[24]=ans时没有可行解!
> 此外,值得注意的是,当得到的s[24]>ans时,虽然s[24]不一定是最优解,但把ans置成s[24]后,确实是可行解。
> 
> 所以,简单把(2)置换成(2')是有问题的!
> 为了等价原命题,必须再加上条件:s[24]>=ans
> 这就是所谓加出来的那条边(5) s[24]-s[0]>=ans
> 
> 最后说一下,SPFA后判dis[24]==ans其实是没有必要的。
----------------------------------------------------------
谢谢大牛,我也有些明白为什么加上了那条诡异的边。
简而言之,如果不加s[24]>=ans这个约束条件,在求完最长路之后,s[24]可能会小于ans,当小于ans就有可能不会满足(2)式,所以此时求出的解也就是错误解,但是这不代表s[24]>=ans时没有可行解。
不说了,越说越像大牛说的,我已经简而言之不下去了,还是看大牛说的吧,说的不能再简单了。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator