学步园

[题目描述] 略

[分析]略

没什么好说的,一道裸题罢了.NOIP前一周还是温习一些知识吧,虽然NOIP一定不会考...

唯一需要注意的是对环的处理,一遍拓补排序即可.

最大流的模板是自己YY的,感觉上跟以前写的完全不一样(以前主要是模仿盾盾的),看来这几个月还是有进步的.

Code:

program pvz;
type int=longint;
const max=maxlongint>>3;
var
        time,tot,l,r,p,o,ans,x,y,i,j,k,m,n,tt:int;
        h,d,now,w:array[0..20000]of int;
        q,a,b:array[1..100000]of int;
        ne,t,g:array[-500000..500000]of int;

function f(x,y:int):int;
begin
        f:=x*m+y+1;
end;

procedure link(a,b,c:int);
begin
        inc(tot);ne[tot]:=h[a];h[a]:=tot;
        t[tot]:=b;g[tot]:=c;tot:=-tot;
        ne[tot]:=h[b];h[b]:=tot;
        t[tot]:=a;g[tot]:=0;tot:=-tot;
end;

function BFS:boolean;
begin
        inc(time);l:=0;r:=1;d[0]:=time;q[1]:=0;
        repeat
                inc(l);i:=q[l];j:=h[i];
                while j<>0 do begin
                        if(g[j]<>0)and(d[t[j]]<d[0])then begin
                                inc(r);q[r]:=t[j];d[t[j]]:=d[i]+1;
                                if d[i]=time then inc(time);
                        end;
                        j:=ne[j];
                end;
        until l=r;
        BFS:=d[tt]>d[0];
end;

procedure extend;var flow:int=max;
begin
        for i:=1 to p do if g[now[i]]<flow then begin
                o:=i;flow:=g[now[i]];
        end;
        for i:=1 to p do begin
                dec(g[now[i]],flow);
                inc(g[-now[i]],flow);
        end;
end;

procedure DFS;
begin
        p:=1;q[p]:=0;now[p]:=h[0];
        while d[0]<>-1 do begin
                j:=now[p];
                while(j<>0)and((g[j]=0)or(d[t[j]]<>d[q[p]]+1))do j:=ne[j];
                if j<>0 then begin
                        now[p]:=j;inc(p);q[p]:=t[j];now[p]:=h[t[j]];
                        if t[j]=tt then begin
                                dec(p);extend;p:=o;now[p]:=ne[now[p]];
                        end;
                end else begin
                        d[q[p]]:=-1;dec(p);now[p]:=ne[now[p]];
                end;
        end;
end;

procedure TopSort;
begin
        for i:=1 to tt-1 do if d[i]=0then begin
                inc(r);q[r]:=i;
        end;
        while l<r do begin
                inc(l);i:=q[l];
                j:=h[i];
                while j<>0 do begin
                        if j<0 then begin
                                dec(d[t[j]]);
                                if d[t[j]]=0 then begin
                                        inc(r);q[r]:=t[j];
                                end;
                        end;
                        j:=ne[j];
                end;
        end;
        for i:=1 to tt-1 do if d[i]<>0 then w[i]:=-max;
end;

procedure DELETE;var st:ansistring;
begin
        p:=0;
        for i:=1 to n*m do begin
                read(w[i]);read(k);
                for j:=1 to k do begin
                        read(x,y);
                        link(f(x,y),i,max);
                        inc(d[f(x,y)]);
                end;
                if i mod m<>1 then begin
                        link(i-1,i,max);inc(d[i-1]);
                end;
        end;
        TopSort;
        fillchar(d,sizeof(d),0);
end;

begin
        assign(input,'pvz.in');reset(input);
        assign(output,'pvz.out');rewrite(output);
        read(n,m);tot:=0;tt:=n*m+1;
        DELETE();
        for i:=1 to n*m do
                if w[i]>=0 then link(0,i,w[i])
                        else link(i,tt,-w[i]);
        while BFS do DFS;
        ans:=0;
        for i:=1 to tt do if d[i]>=d[0]then inc(ans,w[i]);
        write(ans);
        close(input);close(output);
end.