BZOJ 1565 植物大战僵尸(最大权闭合图)

时间:2023-02-20 10:09:20

题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1565

题意:植物大战僵尸,一个n*m的格子,每 个格子里有一个植物,每个植物有两个属性:(1)价值;(2)保护集合,也就是这个植物可以保护矩阵中的某些格子。现在你是僵尸,你每次只能从(i,m) 格子进入,从右向左进攻。若一个格子是被保护的那么你是不能进入的。每进入一个格子则吃掉该格子的植物并得到其价值(价值有可能是负的)。注意,每次在进 入一行后还可以再退到最右侧然后再换一行吃别的。问最大价值是多少?

思路:(1)首先,我们说下啥是最大权闭合 图。在一个有向图中,每个点集有一个权值。要求选择一个点集使得权值最大。选出的点满足,对于任何一条边<u,v>,若选择了u则必须选择 v。满足这个条件的顶点集叫做最大权闭合子图。在下图中,最大的权闭合子图为{3,4,5},价值为4。

BZOJ 1565 植物大战僵尸(最大权闭合图)

(2)如何求最大权闭合子图?构图方法:增
加原点s和汇点t。原图中的权值x大于0的点,连边<s,i,x>,权值为负的点连边<i,t,-x>。原图中的边权值INF。
上图改造后得到的是下面的图。设新图中与s相连的点的权值和为sum,新图的最小割即最大流为w,则答案为sum-w。下图的sum=12,w=8。

BZOJ 1565 植物大战僵尸(最大权闭合图)

(3)最大权闭合图强调的是点之间的依赖关
系,即选择某个点必须选择另外某些点。在本题中,恰有这样的性质。比如,僵尸必须从右向左,因此,选择左侧的点,就必须选择右侧的点;某个格子被另外的一
些格子保护,那么要选择这个格子,必须要先选择另外的那些格子。我们正好可以用这个性质建立图进行求解。另外,在本题中有可能存在环,即比如同一行右侧的
点被左侧的点保护,那么是无法吃掉这些位置的植物的。因此,首先拓扑排序一次,标记哪些格子不在环中。那么只有这些点是可以到达的。

struct node
{
int v,next,cap;
}; node edges[N*100];
int head[N],e;
int pre[N],curedge[N],h[N],num[N];
int s,t; void add(int u,int v,int cap)
{
edges[e].v=v;
edges[e].cap=cap;
edges[e].next=head[u];
head[u]=e++;
} void Add(int u,int v,int cap)
{
add(u,v,cap);
add(v,u,0);
} int visit[N]; int Maxflow(int s,int t,int n)
{
clr(h,0); clr(num,0);
int i;
FOR0(i,n+1) curedge[i]=head[i];
int u=s,Min,k,x,ans=0;
while(h[u]<n)
{
if(u==t)
{
Min=INF+1;
for(i=s;i!=t;i=edges[curedge[i]].v)
{
x=curedge[i];
if(edges[x].cap<Min)
{
Min=edges[x].cap;
k=i;
}
}
ans+=Min; u=k;
for(i=s;i!=t;i=edges[curedge[i]].v)
{
x=curedge[i];
edges[x].cap-=Min;
edges[x^1].cap+=Min;
}
}
for(i=curedge[u];i!=-1;i=edges[i].next)
{
if(edges[i].cap>0&&h[u]==h[edges[i].v]+1)
{
break;
}
}
if(i!=-1)
{
curedge[u]=i;
pre[edges[i].v]=u;
u=edges[i].v;
}
else
{
if(--num[h[u]]==0) break;
curedge[u]=head[u];
x=n;
for(i=head[u];i!=-1;i=edges[i].next)
{
k=edges[i].v;
if(edges[i].cap>0&&h[k]<x) x=h[k];
}
h[u]=x+1; num[x+1]++;
if(u!=s) u=pre[u];
}
}
return ans;
} int a[55][55],n,m;
vector<int> g[N];
int d[N],p[N],sum; void build()
{
sum=0; s=0; t=n*m+1; clr(head,-1); e=0;
int i,j,x;
FOR1(i,n*m) if(visit[i]) FOR0(j,SZ(g[i]))
{
x=g[i][j];
if(visit[x]) Add(x,i,INF);
}
FOR1(i,n*m) if(visit[i])
{
if(p[i]>0) Add(s,i,p[i]),sum+=p[i];
if(p[i]<0) Add(i,t,-p[i]);
}
} int main()
{
RD(n,m);
int i,j;
FOR1(i,n) FOR1(j,m) a[i][j]=(i-1)*m+j;
FOR1(i,n)
{
FOR1(j,m-1)
{
g[a[i][j+1]].pb(a[i][j]);
d[a[i][j]]++;
}
}
int x,r,c;
FOR1(i,n) FOR1(j,m)
{
RD(x); p[a[i][j]]=x;
RD(x);
while(x--)
{
RD(r,c); r++; c++;
g[a[i][j]].pb(a[r][c]);
d[a[r][c]]++;
}
}
queue<int> Q;
FOR1(i,n*m) if(!d[i]) Q.push(i);
while(!Q.empty())
{
x=Q.front();
Q.pop(); visit[x]=1;
FOR0(i,SZ(g[x]))
{
c=g[x][i];
if(--d[c]==0) Q.push(c);
}
}
build();
PR(sum-Maxflow(s,t,t+1));
}