裸的最大权闭合图，但是预处理比较恶心，我WA了好久。首先如果A保护B，那么就连一条A-->B的边，然后对这个图做拓扑序，把环给去掉（拓扑序算法结束后余下的点集便是环集），接下来对于每个换上的点作DFS，把被它保护的点和间接被它保护的点都去掉。然后对于余下的图进行网络流操作，见图如下：
1.如果A保护B则连一条B-->A流量为无穷大的边。
2.如果A的点权>0则连一条S-->A流量为A的点权的边。
3.如果A得点权<0则连一条A-->T流量为A的点权的绝对值的边。
以上操作的要求是AB均为没有被删去的点。然后跑一便最大流，最大流量为maxflow，令tot为所有点权为正的点的点权之和。则答案就是tot-maxflow
program p1565; const maxn=100000000; type bian=record next,point,f:longint; end; var b:array[0..2000000] of bian; p,f,inw,dst:array[0..10000] of longint; x:array[1..10000] of longint; pd,bo:array[0..100000] of boolean; tot,len,i,j,n,m,k,k1,k2:longint; procedure ade(k1,k2,k3:longint); begin inc(len); b[len].f:=k3; b[len].point:=k2; b[len].next:=p[k1]; p[k1]:=len; end; function bfs:boolean; var k1,k2,k3,now,head,i,j:longint; begin fillchar(pd,sizeof(pd),false); pd[0]:=true; head:=1; now:=0; x[1]:=0; dst[0]:=0; while now<head do begin inc(now); i:=p[x[now]]; while i>-1 do begin k1:=b[i].point; if (pd[k1]=false) and (b[i].f>0) and (bo[k1]=true)then begin pd[k1]:=true; dst[k1]:=dst[x[now]]+1; if k1=n+1 then exit(true); inc(head); x[head]:=k1; end; i:=b[i].next; end; end; exit(pd[n+1]); end; function min(k1,k2:longint):longint; begin if k1<k2 then exit(k1) else exit(k2); end; function change(k1,k2:longint):longint; var now,i,j,k:longint; begin if (k1=n+1) or (k2=0) then exit(k2); now:=p[k1]; j:=0; while now>-1 do begin i:=b[now].point; if (b[now].f>0) and (dst[k1]=dst[i]-1) and (bo[i]=true)then begin k:=change(i,min(b[now].f,k2)); k2:=k2-k; j:=j+k; b[now].f:=b[now].f-k; inc(b[now xor 1].f,k); if k2=0 then break; end; now:=b[now].next; end; if j=0 then dst[k1]:=-1; exit(j); end; function dinic:longint; var num,i:longint; begin num:=0; while bfs=true do begin num:=num+change(0,maxn); end; exit(num); end; procedure add(k1,k2,k3:longint); begin inc(inw[k1]); ade(k1,k2,k3); ade(k2,k1,0); end; procedure delete(k:longint); var i,j:longint; begin i:=p[k]; while i<>-1 do begin j:=b[i].point; if i mod 2=1 then dec(inw[j]); i:=b[i].next; end; end; function findmin:longint; var i,j:longint; begin for i:=1 to n do if (inw[i]=0) and (bo[i]=false) then exit(i); exit(0); end; procedure dfs(k:longint); var i,j:longint; begin pd[k]:=true; bo[k]:=false; i:=p[k]; while i<>-1 do begin j:=b[i].point; if (pd[j]=false) and (i mod 2=1) then dfs(j); i:=b[i].next; end; end; begin readln(n,m); fillchar(b,sizeof(b),0); fillchar(p,sizeof(p),-1); fillchar(dst,sizeof(dst),0); fillchar(inw,sizeof(inw),0); len:=-1; for i:=1 to n*m do begin read(f[i],k); for j:=1 to k do begin read(k1,k2); add(k1*m+k2+1,i,maxn); end; end; for i:=0 to n-1 do for j:=0 to m-2 do add(i*m+j+1,i*m+j+2,maxn); n:=n*m; fillchar(bo,sizeof(bo),false); while true do begin k:=findmin; if k=0 then break; bo[k]:=true; delete(k); end; tot:=0; fillchar(pd,sizeof(pd),false); for i:=1 to n do if (bo[i]=false) and (pd[i]=false) then dfs(i); for i:=1 to n do begin if bo[i]=false then continue; if f[i]>0 then begin add(0,i,f[i]); tot:=tot+f[i]; end else if f[i]<0 then add(i,n+1,-f[i]); end; bo[0]:=true; bo[n+1]:=true; tot:=tot-dinic; if tot<0 then tot:=0; writeln(tot); end.
评论 (0)
