Var n,m,temp,i,j,k,t,z,ans,flow,st,ed,t1,t2:Longint;
can:boolean;
E,C:array[0..700,0..700] of Longint;
V,B:array[0..700] of Boolean;
Dfn,Low,F,Stack,H,G:array[0..700] of Longint;
Function AC_Min(a,b:Longint):Longint;
Begin
If a<b then Exit(a) else Exit(b);
End;
Function AC_Pre(a,b:Longint):Longint;
Begin
Exit((a-1)*m+b);
End;
Procedure AC_Sap(k:Longint);
Var temp,i:Longint;
Begin
temp:=flow;
If k=ed then
Begin
Dec(ans,flow); can:=true; Exit;
End;
For i:=1 to ed do
If C[k,i]>0 then
Begin
If H[i]+1=H[k] then
Begin
flow:=AC_Min(flow,C[k,i]);
AC_Sap(i);
If H[st]>=ed Then Exit;
If can then Break;
End;
flow:=temp;
End;
If can then
Begin
Dec(C[k,i],flow); Inc(C[i,k],flow);
End
Else
Begin
Dec(G[H[k]]);If G[H[k]]<=0 then H[st]:=ed;
Inc(H[k]); Inc(G[H[k]]);
End;
End;
Procedure AC_Trajan(k:Longint);
Var i:Longint;
Begin
Inc(t); Dfn[k]:=t; Low[k]:=t; Inc(z); Stack[z]:=k;
V[k]:=true;
For i:=1 to E[k,0] do
Begin
If not(V[E[k,i]]) then AC_Trajan(E[k,i]);
Low[k]:=AC_Min(Low[k],Low[E[k,i]]);
End;
If Dfn[k]=Low[k] then
Begin
If Stack[z]=k then
Begin
Dec(z); Low[k]:=oo; Exit;
End;
Repeat
Low[Stack[z]]:=oo; B[Stack[z]]:=true;
Dec(z);
Until Stack[z+1]=k;
End;
End;
Procedure AC_Dfs(k:Longint);
Begin
If B[k] or V[k] then Exit; V[k]:=true;
IF (k mod m<>1) then AC_Dfs(k-1);
End;
BEGIN
Readln(n,m);
For i:=1 to n do
For j:=1 to m do
Begin
temp:=AC_Pre(i,j);
Read(F[temp]); Read(E[temp,0]);
for k:=1 to E[temp,0] do
Begin
Read(t1,t2);
E[temp,k]:=AC_Pre(t1+1,t2+1);
End;
If j<>1 then
Begin
inc(E[temp,0]); E[temp,E[temp,0]]:=AC_Pre(i,j-1);
End;
End;
For i:=1 to n do
For j:=1 to m do
Begin
If not(V[AC_Pre(i,j)]) then AC_Trajan(AC_Pre(i,j));
End;
Fillchar(V,sizeof(V),false);
For i:=1 to n do AC_Dfs(AC_Pre(i,m));
st:=n*m+1; ed:=n*m+2;
For i:=1 to n do
For j:=1 to m do
Begin
temp:=AC_Pre(i,j); If not(V[temp]) then Continue;
For k:=1 to E[temp,0] do
Begin
If V[E[temp,k]] then C[E[temp,k],temp]:=oo;
End;
If F[temp]>0 then
Begin
Inc(ans,F[temp]); C[st,temp]:=F[temp];
End
Else C[temp,ed]:=-F[temp];
End;
G[0]:=n*m+2;
While H[st]<ed do
Begin
flow:=oo; can:=false; AC_Sap(st);
End;
Writeln(ans);
END.
就是最大权闭合图模型。。
上网查的,看不懂