正题

题目链接:https://www.luogu.com.cn/problem/P2805

---

题目大意

$n\ast m$的格子，攻击这个格子$(x,y)$可以获得价值$c_{x,y}$，攻击一个格子$(x,y)$前要攻击$(x,y+1)$。

对于有的格子$(x,y)$会保护些格子，攻击一个格子直接必须攻击掉保护它的格子。

求最大价值

---

解题思路

先用拓扑排序去掉一些无法攻击的格子(相互保护或者被相互保护的格子保护的)。

然后就是最大权闭合图的问题就好了，跑网络流

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define p(x,y) ((x-1)*m+y) using namespace std; const int N=30*40,inf=2e9; struct node{int to,next,w; }a[N*N]; int ls[N],dep[N],tot=1,n,m,ans,s,e,in[N],edge[N][N],c[N],v[N][N]; queue<int>q; void add_edge(int x,int y,int w) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0; } bool bfs() {memset(dep,0,sizeof(dep));while(!q.empty())q.pop();q.push(s);dep[s]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[y]||!a[i].w) continue;q.push(y);dep[y]=dep[x]+1;if(y==e) return 1;}}return 0; } int dinic(int x,int flow){int rest=0,k;if(x==e) return flow;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[x]+1==dep[y]&&a[i].w){rest+=(k=dinic(y,min(a[i].w,flow-rest)));a[i].w-=k;a[i^1].w+=k;if(rest==flow) return flow;} }if(!rest) dep[x]=0;return rest; } void net_flow(){while(bfs())ans-=dinic(s,inf); } void init(){scanf("%d%d",&n,&m);s=p(n,m)+1;e=s+1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int k;scanf("%d%d",&c[p(i,j)],&k);if(c[p(i,j)]>=0) edge[s][p(i,j)]=c[p(i,j)];if(c[p(i,j)]<0) edge[p(i,j)][e]=-c[p(i,j)];while(k--){int x,y;scanf("%d%d",&x,&y);x++;y++;v[p(i,j)][p(x,y)]++;edge[p(x,y)][p(i,j)]=inf,in[p(x,y)]++;}if(j<m) v[p(i,j+1)][p(i,j)]++,edge[p(i,j)][p(i,j+1)]=inf,in[p(i,j)]++;} } void top_sort(){for(int i=1;i<s;i++)if(!in[i])q.push(i);while(!q.empty()){int x=q.front();q.pop();for(int y=1;y<s;y++){if(!v[x][y]) continue;in[y]-=v[x][y];if(!in[y])q.push(y);}} } void build_graph(){for(int i=1;i<s;i++)if(!in[i]&&c[i]>0)ans+=c[i];for(int i=1;i<=e;i++)for(int j=1;j<=e;j++) if(edge[i][j]&&!in[i]&&!in[j])add_edge(i,j,edge[i][j]); } int main() {init();top_sort();build_graph();net_flow();printf("%d",ans); } 创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的P2805-[NOI2009]植物大战僵尸【网络流,最大权闭合图】的全部内容，希望文章能够帮你解决所遇到的问题。

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