这题应该分两步来做:

1、拓扑排序,去掉无敌点

2、求最大闭合子图

需要注意几点:

1、拓扑排序时,如果(i,j)可以攻击到(x,y),那么增加(x,y)的入度,而不是(i,j)的入度

因为入度代表着要攻击它需要事先攻击几个点

2、求最大闭合子图时,用所有的正权点-最大流

3、求最大闭合子图时,如果(i,j)可以攻击到(x,y),那么连一条边(x,y)到(i,j),容量为正无穷

因为在最大闭合子图中边(x,y)到(i,j)意味着选(x,y)就必须要选(i,j),这与实际含义相符

4、s到正权点,容量为正权点的点权

负权点到t,容量为负权点的点权的绝对值

5、要做好对数据规模的估计

代码:

 type node=record
go,next,c:longint;
end;
var e:array[..] of node;
head,tail,i,n,m,j,tot,max,ans,s,t,x,y:longint;
w,cur,first,inp,q,h:array[..] of longint;
can:array[..] of boolean;
a:array[..,..] of longint;
procedure insert(x,y,z:longint);
begin
inc(tot);
e[tot].go:=y;
e[tot].c:=z;
e[tot].next:=first[x];
first[x]:=tot;
inc(tot);
e[tot].go:=x;
e[tot].c:=;
e[tot].next:=first[y];
first[y]:=tot;
end;
function min(x,y:longint):longint;
begin
if x<y then exit(x) else exit(y);
end;
procedure init;
begin
readln(n,m);
fillchar(inp,sizeof(inp),);
for i:= to n*m do
begin
read(w[i]);read(a[i,]);
for j:= to a[i,] do
begin
read(x,y);inc(x);inc(y);
a[i,j]:=(x-)*m+y;
inc(inp[(x-)*m+y]);
end;
if i mod m<> then
begin
inc(a[i,]);a[i,a[i,]]:=i-;inc(inp[i-]);
end;
readln;
end;
end;
procedure topsort;
begin
head:=;tail:=;
fillchar(q,sizeof(q),);
fillchar(can,sizeof(can),false);
for i:= to n*m do
if inp[i]= then
begin
can[i]:=true;inc(tail);q[tail]:=i;
end;
while head<tail do
begin
inc(head);
x:=q[head];
for i:= to a[x,] do
begin
y:=a[x,i];
dec(inp[y]);
if inp[y]= then
begin
can[y]:=true;
inc(tail);
q[tail]:=y;
end;
end;
end;
end;
procedure makegraph;
begin
max:=;
for i:= to n*m do
if can[i] then
begin
if w[i]> then inc(max,w[i]);
for j:= to a[i,] do
begin
y:=a[i,j];
if can[y] then insert(y,i,maxlongint>>);
end;
if w[i]> then insert(s,i,w[i])
else insert(i,t,-w[i]);
end;
end;
function bfs:boolean;
var i,x,y:longint;
begin
fillchar(h,sizeof(h),);
fillchar(q,sizeof(q),);
head:=;tail:=;q[]:=s;h[s]:=;
while head<tail do
begin
inc(head);
x:=q[head];
i:=first[x];
while i<> do
begin
y:=e[i].go;
if (h[y]=) and (e[i].c<>) then
begin
h[y]:=h[x]+;
inc(tail);
q[tail]:=y;
end;
i:=e[i].next;
end;
end;
exit(h[t]<>);
end;
function dfs(x,f:longint):longint;
var i,y,tmp,used:longint;
begin
if (x=t) or (f=) then exit(f);
i:=cur[x];tmp:=;used:=;
while i<> do
begin
y:=e[i].go;
if (h[y]=h[x]+) and (e[i].c<>) then
begin
tmp:=dfs(y,min(e[i].c,f-used));
dec(e[i].c,tmp);
inc(e[i xor ].c,tmp);
if e[i].c<> then cur[x]:=i;
inc(used,tmp);
if used=f then exit(f);
end;
i:=e[i].next;
end;
if used= then h[x]:=-;
exit(used);
end; procedure dinic;
begin
while bfs do
begin
for i:= to n*m+ do cur[i]:=first[i];
inc(ans,dfs(s,maxlongint>>));
end;
end; procedure main;
begin
tot:=;
s:=;t:=n*m+;
topsort;
makegraph;
dinic;
writeln(max-ans);
end;
begin
init;
main;
end.
05-11 15:10