program net_flow;
//Completed using 2 hrs. Programmed by Hob.Den
//For Celebration
uses math;
type markt=record
p,drt:longint;
vis:boolean;
end;
var c,f:array[0..500,0..500] of longint; //Containage & Flow
n,st,trm,m,a,b:longint; //Nodes,start,termination,edges
mark:array[0..500] of markt; //As its name
procedure init;
var a,b,t1,t2,t3:longint;
begin
fillchar(c,sizeof(c),255);
readln(n,m);
st:=1;
trm:=m+n+2;
for a:=2 to n+1 do begin
b:=1;
while b<>0 do begin
read(b);
if b<>0 then begin
c[a,n+1+b]:=1;
c[n+1+b,a]:=0; end;
end;
end;
for a:=2 to n+1 do begin
c[1,a]:=1; c[a,1]:=0;
end;
for a:=n+2 to m+n+1 do begin
c[a,trm]:=1; c[trm,a]:=0;
end;
end;//Init //It requires inputing adjoining matrix
procedure ford;
var flag,addtrm:boolean;
que:array[0..600] of longint;
he,tl,a,b,head,d,findrt,ipos,tim:longint;
begin
tim:=0;
repeat
inc(tim);
flag:=true;
fillchar(mark,sizeof(mark),0);
fillchar(que,sizeof(que),0);
with mark[1] do begin
p:=0; drt:=maxlongint shr 4;
vis:=true;
end;
he:=0;
tl:=1;
que[tl]:=1;
addtrm:=false;
//Set env for marking
while (not addtrm)and(he<tl) do
begin
inc(he);
head:=que[he];
for a:=1 to m+n+2 do
if (c[head,a]<>-1)and(not mark[a].vis)
then begin
if c[head,a]=0 then
begin
d:=f[a,head];
if d<>0 then begin
mark[a].vis:=true;
mark[a].p:=-head;
mark[a].drt:=min(d,mark[head].drt);
inc(tl);
que[tl]:=a;
if a=trm then addtrm:=true;
end;
end
else begin
d:=c[head,a]-f[head,a];
if d<>0 then begin
mark[a].vis:=true;
mark[a].p:=head;
mark[a].drt:=min(d,mark[head].drt);
inc(tl);
que[tl]:=a;
if a=trm then addtrm:=true;
end;
end;
end; //End for_if
end;//End while
//Main process of marking
if not addtrm then flag:=false
else begin
findrt:=mark[trm].drt;
ipos:=trm;
repeat
if mark[ipos].p<0 then dec(f[-mark[ipos].p,ipos],findrt);
if mark[ipos].p>0 then inc(f[mark[ipos].p,ipos],findrt);
ipos:=abs(mark[ipos].p);
until ipos=st;
end;
//Improving "improvable chain"
until not flag;
end;//Ford
procedure print;
var a,b:longint;
begin
b:=0;
for a:=1 to n+m+2 do inc(b,f[1,a]);
writeln(b);
end;//Print
begin
init;
ford;
print;
end.
测试结果1: 通过本测试点|有效耗时297ms
测试结果2: 通过本测试点|有效耗时172ms
测试结果3: 通过本测试点|有效耗时172ms
测试结果4: 通过本测试点|有效耗时172ms
测试结果5: 通过本测试点|有效耗时171ms
测试结果6: 通过本测试点|有效耗时172ms
测试结果7: 通过本测试点|有效耗时203ms
测试结果8: 测试结果错误.错误结果为:165
正确结果应为:164
测试结果9: 测试结果错误.错误结果为:183
正确结果应为:182
测试结果10: 通过本测试点|有效耗时219ms