讨论 / 求题解
code_beauty 2011-05-30 22:05:00
点我顶贴 收藏 删除
谁过了发个题解啊
#1 小小小学生.c@2010-07-25 12:00:00
回复 删除
哪题?
#2 louxiaoke@2010-07-25 13:13:00
回复 删除
到底哪题

到底哪题

#3 LostInForever@2011-05-30 22:04:00
回复 删除
现在有了,自己看。

我发的

#4 LostInForever@2011-05-30 22:05:00
回复 删除
[417]本题正解——用最大流求解即可

初初看到每个同学有一个“传递张数限制”,便很自然地想到顶点容量限制,进而想到最大流+拆点。

顺着这个思路,以小舟为源点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.

查看更多回复
提交回复