[洛谷 2805][NOI2009]植物大战僵尸

题目链接

https://www.luogu.com.cn/problem/P2805

题解

读完题后可以发现,要想消灭植物 \(u\),需要消灭这两种保护 \(u\) 的植物:

  1. 在 \(u\) 前面的植物。
  2. 攻击范围包括 \(u\) 的植物。

如果 \(u\) 保护 \(v\),就从 \(u\) 向 \(v\) 连一条边。

这样连出来的图可能有环,环上的点都需要被剔除(显然这些点都不可能被取)。

如果我们将剔除环上的点得到的图上的所有边方向取反的话,就会发现我们求的其实是整个图的最大权闭合子图。

求最大权闭合子图的方法可以看 这个

#include <cstring>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
 int v,w,next;
}e[1000005];
int n,m,s,t,cnt=1;
int head[1005],dep[1005],vis[1005],cur[1005],pr[1005],tot[1005],ans;
vector<int> e1[1005];
void addedge(int u,int v,int w)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].next=head[u];
 head[u]=cnt;
}
bool bfs()
{
 queue<int> q;
 memset(dep,INF,sizeof(dep));
 memset(vis,0,sizeof(vis));
 memcpy(cur,head,sizeof(head));
 dep[s]=0;
 vis[s]=1;
 q.push(s);
 while(!q.empty())
 {
  int p=q.front();
  q.pop();
  vis[p]=0;
  for(int i=head[p];i;i=e[i].next)
   if(dep[e[i].v]>dep[p]+1&&e[i].w)
   {
    dep[e[i].v]=dep[p]+1;
    if(!vis[e[i].v])
    {
     vis[e[i].v]=1;
     q.push(e[i].v);
    }
   }
 }
 if(dep[t]==INF)return 0;
 return 1;
}
int dfs(int p,int w)
{
 if(p==t)return w;
 int used=0;
 for(int i=cur[p];i;i=e[i].next)
 {
  cur[p]=i;
  if(dep[e[i].v]==dep[p]+1&&e[i].w)
  {
   int flow=dfs(e[i].v,min(w-used,e[i].w));
   if(flow)
   {
    used+=flow;
    e[i].w-=flow;
    e[i^1].w+=flow;
    if(used==w)break;
   }
  }
 }
 return used;
}
int f(int x,int y)
{
 return x*m+y+1;
}
void topo()
{
 queue<int> q;
 for(int i=1;i<=n*m;i++)
  if(!tot[i])q.push(i);
 while(!q.empty())
 {
  int u=q.front();
  q.pop();
  if(pr[u]>=0)
   addedge(s,u,pr[u]),addedge(u,s,0),ans+=pr[u];
  else
   addedge(u,t,-pr[u]),addedge(t,u,0);
  for(auto v:e1[u])
  {
   addedge(v,u,INF),addedge(u,v,0);
   tot[v]--;
   if(!tot[v])q.push(v);
  }
 }
}
int main()
{
 cin>>n>>m;
 s=m*n+1,t=m*n+2;
 for(int i=0;i<n;i++)
  for(int j=0;j<m;j++)
  {
   int u=f(i,j),v=f(i,j+1),w;
   cin>>pr[u]>>w;
   if(j!=m-1)
    e1[v].push_back(u),tot[u]++;
   while(w--)
   {
    int x,y;
    cin>>x>>y;
    v=f(x,y);
    e1[u].push_back(v),tot[v]++;
   }
  }
 topo();
 while(bfs())
  ans-=dfs(s,INF);
 cout<<ans<<endl;
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据