题目大意
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）更多的出纳员在工作。
输入
输入文件的第一行为测试点个数（<= 20）。每组测试数据的第一行为24 个整数表示R（0），R（1），…， R（23）（R（I）<= 1000）。接下来一行是N，表示申请者数目（0 <= N <= 1000），接下来每行包含一个整数tI （0 <= tI <= 23）。两组测试数据之间没有空行。
输出
对于每个测试点，输出只有一行，包含一个整数，表示需要出纳员的最少数目。如果无解，你应当输出“No Solution”。
分析
调了一个上午，发现只是flaj打成了flag 立的一手好flag
我们的资料和这位是一样的——点一下
code
const
maxe=
600;
maxv=
15000;
type
arr=
record
x,y,w,next:longint;
end;
var
n,m,s:longint;
nm:longint;
a:
array[
0..maxv]
of arr;
d:
array[
0..maxe]
of int64;
v1:
array[
0..maxe]
of longint;
ls:
array[
0..maxe]
of longint;
stick:
array[
0..maxv]
of longint;
head,tail:longint;
x,y,w:
array[
0..
30]
of longint;
i,j,k:longint;
flag:boolean;
flaj:
array[
0..maxe]
of longint;
max:longint;
t:longint;
fff:boolean;
procedure relax(u,v,w:longint);
begin
if d[u]+w>d[v]
then
begin
d[v]:=d[u]+w;
if v1[v]=
0
then begin
head:=head+
1;
stick[head]:=v;
flaj[v]:=flaj[v]+
1;
v1[v]:=
1;
end;
end;
end;
procedure spfa;
var
i,j:longint;
begin
for i:=
0 to 30 do
d[i]:=-maxlongint;
fillchar(stick,sizeof(stick),
0);
fillchar(flaj,sizeof(flaj),
0);
fillchar(v1,sizeof(v1),
0);
flag:=
false;
head:=
1;
stick[head]:=
0;
d[
0]:=
0;
v1[
0]:=
1;
repeat
j:=stick[head];
i:=ls[stick[head]];
head:=head-
1;
while i<>
0 do
with a[i]
do
begin
relax(x,y,w);
if flaj[y]>
30 then
begin
flag:=
true;
exit;
end;
i:=next;
end;
v1[j]:=
0;
until head=
0;
end;
procedure add(x,y,w:longint);
begin
nm:=nm+
1;
a[nm].x:=x;
a[nm].y:=y;
a[nm].w:=w;
a[nm].next:=ls[x];
ls[x]:=nm;
end;
procedure init;
var
i,j,k:longint;
begin
fillchar(x,sizeof(x),
0);
fillchar(y,sizeof(y),
0);
for i:=
1 to 30 do
d[i]:=maxlongint;
for i:=
1 to 24 do
read(x[i]);
readln;
readln(n);
for i:=
1 to n
do
begin
readln(k);
k:=k+
1;
y[k]:=y[k]+
1;
end;
end;
begin
readln(t);
while t<>
0 do
begin
init;
fff:=
true;
for max:=
0 to n
do
begin
fillchar(a,sizeof(a),
0);
fillchar(ls,sizeof(ls),
0);
nm:=
0;
add(
0,
24,max);
for i:=
1 to 24 do
begin
add(i-
1,i,
0);
add(i,i-
1,-y[i]);
end;
for i:=
1 to 8 do
add(i+
16,i,(x[i]-max));
for i:=
9 to 24 do
add(i-
8,i,x[i]);
m:=nm;
spfa;
if (d[
24]=max)
then begin
fff:=
false;
writeln(max);
break;
end;
end;
if fff
then writeln(
'No Solution');
t:=t-
1;
end;
end.
转载请注明原文地址: https://ju.6miu.com/read-968816.html
