讨论 / 题解 pascal
jxxx3341 2017-10-12 23:54:05
点我顶贴 收藏 删除
测试点1 Accepted / 1ms / 10740kB

测试点2 Accepted / 0ms / 10740kB

测试点3 Accepted / 0ms / 10740kB

测试点4 Accepted / 0ms / 10740kB

测试点5 Accepted / 0ms / 10740kB

测试点6 Accepted / 0ms / 10740kB

测试点7 Accepted / 1ms / 10740kB

测试点8 Accepted / 1ms / 10740kB

测试点9 Accepted / 92ms / 10740kB

测试点10 Accepted / 3ms / 10740kB

type

recc=record

x,y,f,next,op:longint;

end;

const oo=10000000;

var

e:array[1..500000] of recc;

no:array[1..80,1..80] of longint;

map:array[0..605,0..605] of boolean;

a,g,h,d,p,num,now:array[0..10000] of longint;

v:array[0..4000] of boolean;

i,j,k,m,n,tyy,s,t,x,y,z,sum:longint;

procedure add(x,y,f:longint);

begin

inc(tyy);

e[tyy].x:=x;e[tyy].y:=y;

e[tyy].f:=f;

e[tyy].next:=h[x];h[x]:=tyy;

inc(tyy);

e[tyy].x:=y;e[tyy].y:=x;

e[tyy].f:=0;

e[tyy].next:=h[y];h[y]:=tyy;

e[tyy].op:=tyy-1;e[tyy-1].op:=tyy;

end;

function isap:longint;

var u,v,i,j,tmp,flow,aug:longint;ff:boolean;

begin

flow:=0;aug:=oo;

for i:=0 to t+1 do

begin

d[i]:=0;p[i]:=-1;

num[i]:=0;now[i]:=h[i];

end;

u:=s;num[0]:=t+1;

while d[s]<t+1 do

begin

ff:=false;i:=now[u];

while i<>0 do

begin

v:=e[i].y;

if (e[i].f>0)and(d[u]=d[v]+1) then

begin

ff:=true;p[v]:=i;

if e[i].f<aug then aug:=e[i].f;

now[u]:=i;u:=v;

if u=t then

begin

flow:=flow+aug;

while u<>s do

begin

j:=p[u];

dec(e[j].f,aug);

inc(e[e[j].op].f,aug);

u:=e[j].x;

end;

aug:=oo;

end;

break;

end;

i:=e[i].next;

end;

if ff then continue;

dec(num[d[u]]);

if num[d[u]]=0 then exit(flow);

tmp:=t+1;i:=h[u];

while i>0 do

begin

v:=e[i].y;

if (e[i].f>0)and(d[v]<tmp) then

begin

tmp:=d[v];now[u]:=i;

end;

i:=e[i].next;

end;

d[u]:=tmp+1;

inc(num[d[u]]);

if u<>s then u:=e[p[u]].x;

end;

exit(flow);

end;

procedure toposort;

var i,j,k,x,y:longint;

begin

fillchar(v,sizeof(v),0);

repeat

k:=-1;

for i:=1 to n*m do

if a[i]=0 then

begin

k:=i;break;

end;

if k=-1 then break;

a[k]:=-1;v[k]:=true;

for i:=1 to n*m do

if map[k,i] and not v[i] then dec(a[i]);

until false;

for i:=1 to n*m do

for j:=1 to n*m do

if v[i] and v[j] and map[i,j] then

add(j,i,oo);

for i:=1 to n do

for j:=1 to m do

if v[no[i,j]] then

begin

k:=g[no[i,j]];

if k>0 then

begin

add(s,no[i,j],k);

sum:=sum+k;

end;

if k<0 then

add(no[i,j],t,-k);

end;

end;

begin

// assign(input,'pvz10.in');reset(input);

readln(n,m);

for i:=1 to n do

for j:=1 to m do

no[i,j]:=(i-1)*m+j;

s:=0;t:=n*m+1;

for i:=1 to n do

for j:=1 to m do

begin

read(g[no[i,j]]);

read(k);

for z:=1 to k do

begin

read(x,y);inc(x);inc(y);

if not map[no[i,j],no[x,y]] then

begin

map[no[i,j],no[x,y]]:=true;

inc(a[no[x,y]]);

end;

end;

end;

for i:=1 to n do

for j:=2 to m do

if not map[no[i,j],no[i,j-1]] then

begin

map[no[i,j],no[i,j-1]]:=true;

inc(a[no[i,j-1]]);

end;

toposort;

writeln(sum-isap);

end.

查看更多回复
提交回复