初初看到每个同学有一个“传递张数限制”,便很自然地想到顶点容量限制,进而想到最大流+拆点。
顺着这个思路,以小舟为源点S,把除小舟外的其他同学i每个拆成两个点i'和i"。
另设汇点T。i'和i"之间连条容量为Wi的边,若i可传给j,则在i"和j'之间连条容量为正无穷大的边。若小舟可以传给i,则在S和i'之间连条容量为正无穷大的边。
对小舟的每个朋友i,由于传给自己的不算在内,故在i'和T之间连条容量为1的边,而不是i"。
最后求一次最大流即可。由于本题数据范围较小(N<=50),故用简单的最短增广路算法也可以AC。
(我提交了三次,三次都AC,大家别拍板砖啊,我只是想借RQNOJ的平台试验最大流算法的优化而已~)
由于本题较特殊,每次增广的都是单位流量,故代码中有些地方可以省略。
附:我第三次提交的PASCAL源程序:
program p417;
var
c,fl:array[0..127,0..127]of longint;
q,pr,bj:array[0..127]of longint;
n,m,k,i,j,f,r,st,ed,t,x,y,fv:longint;
begin
readln(n,m,k);
fillchar(c,sizeof(c),0);
for i:=2 to n do
read(c[2*i-1,2*i]);
readln;
for i:=1 to k do
begin
read(x);c[2*x-1,2]:=1;
end;
readln;
for i:=1 to m do
begin
readln(x,y);
x:=x*2;y:=y*2-1;
if x=2 then x:=1;
c[x,y]:=maxlongint;
end;
st:=1;ed:=2;
fillchar(fl,sizeof(fl),0);
fv:=0;
while true do
begin
f:=1;r:=1;q[r]:=st;
fillchar(bj,sizeof(bj),0);bj[st]:=3;
pr[st]:=0;
while (f<=r)and(bj[ed]=0) do
begin
for i:=1 to n*2 do
if bj[i]=0 then
if (fl[q[f],i]<c[q[f],i]) then
begin
inc(r);q[r]:=i;
bj[i]:=1;
pr[i]:=q[f];
end;
for i:=1 to n*2 do
if bj[i]=0 then
if (fl[i,q[f]]>0) then
begin
inc(r);q[r]:=i;
bj[i]:=2;
pr[i]:=q[f];
end;
inc(f);
end;{while f<=r}
if bj[ed]=0 then break;
inc(fv);
x:=ed;
while x<>st do
begin
y:=pr[x];
if bj[x]=1 then
inc(fl[y,x])
else dec(fl[x,y]);
x:=y;
end;
end;{while true}
writeln(fv);
end.