1755 【差分约束】Cashier Employment(出纳员的雇佣).doc

【差分约束】Cashier Employment（出纳员的雇佣）Time Limit:1000MS Memory Limit:65536KTotal Submit:2 Accepted:2 Description 出纳员的雇佣（cashier.pas/c/cpp） 【问题描述】 Tehran的一家每天24小时营业的超市，需要一批出纳员来满足它的需要。超市经理雇佣你来帮他解决他的问题超市在每天的不同时段需要不同数目的出纳员（例如：午夜时只需一小批，而下午则需要很多）来为顾客提供优质服务。他希望雇佣最少数目的出纳员。 经理已经提供你一天的每一小时需要出纳员的最少数量R(0), R(1), ., R(23)。R（0）表示从午夜到上午1：00需要出纳员的最少数目，R（1）表示上午1：00到2：00之间需要的，等等。每一天，这些数据都是相同的。有N人申请这项工作，每个申请者I在没24小时中，从一个特定的时刻开始连续工作恰好8小时，定义tI （0 = tI =23）为上面提到的开始时刻。也就是说，如果第I个申请者被录取，他（她）将从tI 时刻开始连续工作8小时。 你将编写一个程序，输入R（I）（I = 0.23）和tI （I = 1.N），它们都是非负整数，计算为满足上述限制需要雇佣的最少出纳员数目。在每一时刻可以有比对应的R（I）更多的出纳员在工作。 Input 第一行为测试点个数（= 20）。每组测试数据的第一行为24个整数表示R（0），R（1），.， R（23）（R（I）= 1000）。接下来一行是N，表示申请者数目（0 = N = 1000），接下来每行包含一个整数tI （0 = tI = 23）。两组测试数据之间没有空行。 Output 对于每个测试点，输出只有一行，包含一个整数，表示需要出纳员的最少数目。如果无解，你应当输出“No Solution”。 Sample Input 11 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1502322110Sample Output 1Hint 本题数据不完整，请在本系统测试通过后到 /problem?id=1275 提交完整测试！ Source Tehran 2000解析1:题意: 一家24小时营业的超市,需要一批出纳员来满足它的需求,该超市在每天的不同时刻需要不同数目的出纳员来为顾客提供服务,现在给出一天里每一小时需要出纳员的最少数量r0,r1,r23.r0表示从午夜到上午1:00需要出纳员的最少数目等等,每一天这些数据都是相同的,有n个人申请这项工作,每个申请者i在每天24小时中,从某一个特定的时刻开始连续工作恰好8小时,定义ti(0=ti=0 即在i时刻录用的出纳员数目大于或等于0 si-si-1=sum si-sj=ri 此时ij&i=(j+8)%24 因为在0j时刻雇佣的出纳员连续工作8个小时,此时i=j+8很显然需要重新雇佣出纳员且最小为ri sj-si=sum-ri 此时ii说明可能某一天雇佣的出纳员连续工作8个小时后到了下一天的i时刻,所以从ij=16+i时刻需要雇佣的出纳员数目最大为sum-ri 由于sum是未知的,所以可以根据上述约束条件来构造约束图,为方便建图,以0为起点,由于题目要求的是出纳员的最少数目,所以建图后用Bellman_Ford算法求解单源最长路,在这过程中枚举sum，如果途中不存在环且s24=sum,那么就找到了一个可行解. 将约束条件整理如下: si-si-1=0 si-1-si= -ti i=(1,2,24) s24-s0=sum si-sj=ri ij i=(j-1+8)%24+1 si-sj=ri-sum ij i=(j-1+8)%24+1 Bellman_Ford算法求解最长路,在主程序中枚举sum,就可以得到需要雇佣的出纳员数目的最小值,也可以二分法求解.解析2:设numi为i时刻能够开始工作的人数，xi为实际雇佣的人数， 设ri为i时刻至少需要工作的人数, sI=x1+x2+xI 有如下关系： xI=rI 0=sI-sI-1=numI， 1=I=rI，8=I=rI-sum， 1=I=sum(冯威的论文少了这个条件，看了别人的解题报告，才发现。想想也是，sum是枚举的当前最小值，s24是实际工作的工人，那么其一定大于sum) 解析3:用si表示 从0时刻到i时刻雇的人的总数，ti是在i时刻来应聘 的人，ans 为这一天雇佣的总人数,s-1=0，很容易得到两个约束：在i时刻的雇佣的人一定之能少于等于ti，而且一定大于等于0(只是大于等于0，而不能说大于等于Ri ，因为前面的时刻的人可以流下来到i时刻继续工作)。就是一个人也不雇.0=Si-si-1 si-si-1 =0 ; si-1-si=-ti最后一个小时雇的人肯定要大于等于ans，S23=ans = s23-s-1=ans；真正的8个小时的关系体现在这里：从j时刻雇佣的人工作到i时刻已经走了，那么在j+1时刻就必须雇佣大于等于Ri个人 = si-sj=ri (ij,i=(j+8)%24) & si-sj+ans=ri (ij,i=(j+8)%24)。在这些不等式上面建立约束图，而ans事先不知道，先枚举。如果存在正圈 说明ans小了 因为存在这样的路 w(0,8)=r8 ,w(16,0)=r0-ans 中间的权时0 ，所以增大ans能避免正圈出现，也就是说如果ans=n的时候还出现正圈的话 那么就无解了，二分 就是根据这个单调关系写的 但是 没写出来.程序1： var k,sum,i,j,n,m,x,s:longint; a:array0.1000,1.3 of longint; t,d,r:array0.25 of longint; can:boolean; procedure add(x,y,z:longint); begin inc(s); as,1:=x; as,2:=y; as,3:=z; end; function Bellman_Ford:boolean; var i,j:longint; flag:boolean; begin for i:=1 to 24 do di:=-1000000; d0:=0; for i:=0 to 24 do begin flag:=true; for j:=1 to s do if daj,2daj,1+aj,3 then begin daj,2:=daj,1+aj,3; flag:=false; end; if flag then break; end; for i:=1 to s do if dai,2dai,1+ai,3 then exit(false); if d24=sum then exit(true) else exit(false); end; begin readln(n); for k:=1 to n do begin can:=true; fillchar(a,sizeof(a),0); for i:=1 to 24 do read(ri); readln(m); for i:=1 to m do begin readln(x); inc(tx+1); end; for sum:=0 to m do begin s:=0; for i:=1 to 24 do begin add(i-1,i,0); add(i,i-1,-ti); end; for i:=8 to 24 do add(i-8,i,ri); for i:=1 to 7 do add(i+16,i,ri-sum); add(0,24,sum); if Bellman_Ford then begin writeln(sum); can:=false; break; end; end; if can then writeln(No Solution); end; end.解析4:详细解释一下。为避免负数，时间计数124。令：Ri i时间需要的人数 （1=i=24）Ti i时间应聘的人数 （1=i=24）xi i时间录用的人数 （0=i=24），其中令x0=0再设si=x0+x1+xi （0=i=Ri (8=i=Ri-s24 (1=i=0 (1=i=-Ti (1=i=Ri-ans (1=ians时，虽然s24不一定是最优解，但把ans置成s24后，确实是可行解。所以，简单把(2)置换成(2)是有问题的！为了等价原命题，必须再加上条件：s24=ans这就是所谓加出来的那条边（5） s24s0=ans最后说一下，SPFA后判dis24=ans其实是没有必要的。程序2: (超时,原因是调用add过程时动用a,b数组时间长)type arr=array0.400,0.2 of longint; arr2=array0.24 of longint;var i,x,m,n,s,s2:longint; can:boolean; hash,r,t,d:array0.25 of longint; a,a2:arr; b,b2:arr2; v:array0.25 of boolean;procedure add(x,y,z:longint; var a:arr; var b:arr2);begin inc(s); as,0:=bx; bx:=s; as,1:=y; as,2:=z;end;function spfa(sum:longint):boolean;var i,j,k,t,f:longint; q:array0.100 of longint;begin fillchar(v,sizeof(v),false); fillchar(hash,sizeof(hash),0); s:=s2; a:=a2; b:=b2; add(0,24,sum,a,b); for i:=1 to 7 do add(i+16,i,ri-sum,a,b); for i:=8 to 24 do add(i-8,i,ri,a,b); for i:=1 to 24 do di:=-100000; t:=1; fillchar(q,sizeof(q),0); d0:=0; v0:=true; q1:=0; while t0 do begin i:=qt; dec(t); k:=bi; while k0 do begin j:=ak,1; if di+ak,2dj then begin dj:=di+ak,2; if not vj then begin vj:=true; inc(t); qt:=j; inc(hashqt); if hashqt24 then exit(false); end; end; k:=ak,0; end; vi:=false; end; exit(true);end;begin readln(m); while m0 do begin dec(m); for i:=1 to 24 do read(ri); readln; readln(n); fillchar(t,sizeof(t),0); s:=0; for i:=1 to n do begin read(x); inc(tx+1); end; for i:=1 to 24 do begin add(i-1,i,0,a2,b2); add(i,i-1,-ti,a2,b2); end; can:=false; s2:=s; for i:=0 to n do if spfa(i) then begin can:=true; break; end; if not can then writeln(No Solution) else writeln(i); end;end.程序3：（16ms）var i,j,x,m,n:longint; can:boolean; hash,r,t,d:array0.25 of longint; a,a2:array0.24,0.24 of record x,y:longint; end; v:array0.25 of boolean;function spfa(sum:longint):boolean;var i,j,k,t,f:longint; q:array0.100 of longint;begin fillchar(v,sizeof(v),false); fillchar(hash,sizeof(hash),0); a:=a2; inc(a0,0.x); j:=a0,0.x; a0,j.x:=24; a0,j.y:=sum; for i:=1 to 8 do begin inc(ai+16,0.x); j:=ai+16,0.x; ai+16,j.x:=i; ai+16,j.y:=ri-sum; end; for i:=9 to 24 do begin inc(ai-8,0.x); j:=ai-8,0.x; ai-8,j.x:=i; ai-8,j.y:=ri; end; for i:=1 to 24 do di:=-100000; t:=1; fillchar(q,sizeof(q),0); d0:=0; v0:=true; q1:=0; while t0 do begin i:=qt; dec(t); for j:=1 to ai,0.x do begin k:=ai,j.x; if di+ai,j.ydk then begin dk:=di+ai,j.y; if not vk then begin vk:=true; inc(t); qt:=k; inc(hashqt); if hashqt24 then exit(false); end; end; end; vi:=false; end; exit(true);end;begin readln(m); while m0 do begin dec(m); for i:=1 to 24 do read(ri); readln; readln(n); fillchar(t,sizeof(t),0); for i:=1 to n do begin read(x); inc(tx+1); end; fillchar (a2,sizeof(a2),0); for i:=1 to 24 do begin inc(a2i-1,0.x); j:=a2i-1,0.x; a2i-1,j.x:=i; a2i-1,j.y:=0; inc(a2i,0.x); j:=a2i,0.x; a2i,j.x:=i-1; a2i,j.y:=-ti; end; can:=false; for i:=0 to n do if spfa(i) then begin can:=true; break; end; if not can then writeln(No Solution) else writeln(i); end;end.我觉得是因为他原来的程序过不了所以测试数据，不知怎么搞到了测试数据，发现只有n=4的一个测试用例过不了，而且正确答案是No solution.所有他就加上这一句来AC。 其实，他是忘了加 add(-1,23,ans)这条边。/冯威论文的程序，他的程序有小bug，已经修改。const maxn=230;var g:array-1.maxn,1.4of record n,v:integer; end; d,xu,num,a:array-1.maxnof integer; ans:integer; x,n,casen,o,i:integer; flag:boolean;procedure add(a,b,c:integer); begin inc(numa); ga,numa.n:=b; ga,numa.v:=c; end;procedure init; var i:integer; begin fillchar(g,sizeof(g),0); add(-1,23,ans); /原程序没有加这条边 for i:=0 to