BZOJ1565：[NOI2009]植物大战僵尸——题解

http://www.lydsy.com/JudgeOnline/problem.php?id=1565

https://www.luogu.org/problemnew/show/P2805

Plants vs. Zombies（PVZ）是最近十分风靡的一款小游戏。Plants（植物）和Zombies（僵尸）是游戏的主角，其中Plants防守，而Zombies进攻。该款游戏包含多种不同的挑战系列，比如Protect Your Brain、Bowling等等。其中最为经典的，莫过于玩家通过控制Plants来防守Zombies的进攻，或者相反地由玩家通过控制Zombies对Plants发起进攻。

现在，我们将要考虑的问题是游戏中Zombies对Plants的进攻，请注意，本题中规则与实际游戏有所不同。游戏中有两种角色，Plants和Zombies，每个Plant有一个攻击位置集合，它可以对这些位置进行保护；而Zombie进攻植物的方式是走到植物所在的位置上并将其吃掉。

游戏的地图可以抽象为一个N行M列的矩阵，行从上到下用0到N–1编号，列从左到右用0到M–1编号；在地图的每个位置上都放有一个Plant，为简单起见，我们把位于第r行第c列的植物记为Pr, c。

Plants分很多种，有攻击类、防守类和经济类等等。为了简单的描述每个Plant，定义Score和Attack如下：

Score[Pr, c]

Zombie击溃植物Pr, c可获得的能源。若Score[Pr, c]为非负整数，则表示击溃植物Pr, c可获得能源Score[Pr, c]，若为负数表示击溃Pr, c需要付出能源 -Score[Pr, c]。

Attack[Pr, c]

植物Pr, c能够对Zombie进行攻击的位置集合。

Zombies必须从地图的右侧进入，且只能沿着水平方向进行移动。Zombies攻击植物的唯一方式就是走到该植物所在的位置并将植物吃掉。因此Zombies的进攻总是从地图的右侧开始。也就是说，对于第r行的进攻，Zombies必须首先攻击Pr, M-1；若需要对Pr, c（0≤c<M-1）攻击，必须将Pr,M-1, Pr, M-2 … Pr, c+1先击溃，并移动到位置(r, c)才可进行攻击。

在本题的设定中，Plants的攻击力是无穷大的，一旦Zombie进入某个Plant的攻击位置，该Zombie会被瞬间消灭，而该Zombie没有时间进行任何攻击操作。因此，即便Zombie进入了一个Plant所在的位置，但该位置属于其他植物的攻击位置集合，则Zombie会被瞬间消灭而所在位置的植物则安然无恙（在我们的设定中，Plant的攻击位置不包含自身所在位置，否则你就不可能击溃它了）。

Zombies的目标是对Plants的阵地发起进攻并获得最大的能源收入。每一次，你可以选择一个可进攻的植物进行攻击。本题的目标为，制定一套Zombies的进攻方案，选择进攻哪些植物以及进攻的顺序，从而获得最大的能源收入。

首先把植物看成点，那么这个点有点权，且取这个点必须取它前面的点和保护它的点。

于是这就是最大权闭合子图的模型了。

但是有一个问题，保护可能是一个环，这样你一个点也取不了。

为此需要拓扑排序，剔除这些点。

但是还要注意，拓扑排序的边和最大权闭合子图的边是反的，因为前者中虽然可能出现守护环，但是守护这个环的点可以被吃，如果不反向那么环删不掉的同时守护环的点也会删不掉。

（就因为这个别了半个点……）

#include<algorithm> #include<iostream> #include<cstring> #include<cctype> #include<cstdio> #include<vector> #include<queue> #include<cmath> using namespace std; typedef long long ll; const int N=705; const int M=800005; const int INF=1e9; inline int read(){int X=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } struct node{int nxt,to,w; }edge[M]; int head[N],cnt=-1,S,T; void add(int u,int v,int w){edge[++cnt].to=v;edge[cnt].w=w;edge[cnt].nxt=head[u];head[u]=cnt; } int lev[N],cur[N],dui[N]; bool bfs(int m){int r=0;for(int i=1;i<=m;i++){lev[i]=-1;cur[i]=head[i];}dui[0]=S,lev[S]=0;int u,v;for(int l=0;l<=r;l++){u=dui[l];for(int e=head[u];e!=-1;e=edge[e].nxt){v=edge[e].to;if(edge[e].w>0&&lev[v]==-1){ lev[v]=lev[u]+1;r++;dui[r]=v; if(v==T)return 1; }}}return 0; } int dinic(int u,int flow,int m){if(u==m)return flow;int res=0,delta;for(int &e=cur[u];e!=-1;e=edge[e].nxt){int v=edge[e].to;if(edge[e].w>0&&lev[u]<lev[v]){ delta=dinic(v,min(edge[e].w,flow-res),m); if(delta>0){edge[e].w-=delta;edge[e^1].w+=delta;res+=delta;if(res==flow)break; }}}if(res!=flow)lev[u]=-1;return res; } int n,m,ans,s[N],indeg[N]; queue<int>q; void Topu(){for(int i=1;i<=n*m;i++){if(!indeg[i])q.push(i);}while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i!=-1;i=edge[i].nxt){if(!(i&1))continue;int v=edge[i].to;indeg[v]--;if(!indeg[v])q.push(v);}}for(int i=1;i<=n*m;i++){if(indeg[i]){s[i]=-INF;}} } int main(){memset(head,-1,sizeof(head));n=read(),m=read();S=n*m+1,T=S+1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int now=(i-1)*m+j;s[now]=read();int w=read();for(int k=1;k<=w;k++){int x=read()+1,y=read()+1;int bef=(x-1)*m+y;add(bef,now,INF);add(now,bef,0);indeg[bef]++;}if(j!=m){int bef=now+1;add(now,bef,INF);add(bef,now,0);indeg[now]++;}}}Topu();for(int i=1;i<=n*m;i++){if(s[i]>=0){ans+=s[i];add(S,i,s[i]);add(i,S,0);}else{add(i,T,-s[i]);add(T,i,0);}}while(bfs(T))ans-=dinic(S,INF,T);printf("%d\n",ans);return 0; }

+++++++++++++++++++++++++++++++++++++++++++

 +本文作者：luyouqi233。 　　　　　　　　　　　　　　+

 +欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

转载于:https://www.cnblogs.com/luyouqi233/p/8460949.html

总结

以上是生活随笔为你收集整理的BZOJ1565：[NOI2009]植物大战僵尸——题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。