讨论 / - -
a875797040 2013-02-03 00:34:00
点我顶贴 收藏 删除
这题模型还真是。。裸

连我这种网络流无能力者也在几乎刚读完题就想到了最大权闭合图的模型。。

#1 NEW WORLD@2014-08-21 07:29:47
回复 删除
Const oo=Maxlongint>>1;

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.

就是最大权闭合图模型。。

上网查的,看不懂

查看更多回复
提交回复