题目
现在，我们将要考虑的问题是游戏中 Zombies 对 Plants 的进攻，请注意，本题中规则与实际游戏有所不同。游戏中有两种角色，Plants 和 Zombies，每个 Plant 有一个攻击位置集合，它可以对这些位置进行保护；而 Zombie 进攻植物的方式是走到植物所在的位置上并将其吃掉。
游戏的地图可以抽象为一个 (N) 行 (M) 列的矩阵，行从上到下用 (0) 到 (N–1) 编号，列从左到右用 (0) 到 (M–1) 编号；在地图的每个位置上都放有一个 Plant，为简单起见，我们把位于第 (r) 行第 (c) 列的植物记为 (P_{r, c})。
Plants 分很多种，有「攻击类」「防守类」和「经济类」等等。为了简单的描述每个 Plant，定义 (operatorname{Score}) 和 (operatorname{Attack}) 如下：
-
(operatorname{Score}(P_{r, c})) — Zombie 击溃植物 (P_{r, c}) 可获得的能源。
若 (operatorname{Score}(P_{r, c})) 为非负整数，则表示击溃植物 (P_{r, c}) 可获得能源 (operatorname{Score}(P_{r, c}))，若为负数表示击溃 (P_{r, c}) 需要付出能源 (-operatorname{Score}(P_{r, c}))。 -
(operatorname{Attack}(P_{r, c})) — 植物 (P_{r, c}) 能够对 Zombie 进行攻击的位置集合。
Zombies 必须从地图的右侧进入，且只能沿着水平方向进行移动。Zombies 攻击植物的唯一方式就是走到该植物所在的位置并将植物吃掉。因此 Zombies 的进攻总是从地图的右侧开始。也就是说，对于第 (r) 行的进攻，Zombies 必须首先攻击 (P_{r, M-1})；若需要对 (P_{r, c})（(0 le c < m - 1)）攻击，必须将 (P_{r,M-1}, P_{r, M-2} cdots P_{r, c+1}) 先击溃，并移动到位置 ((r, c)) 才可进行攻击。
在本题的设定中，Plants 的攻击力是无穷大的，一旦 Zombie 进入某个 Plant 的攻击位置，该 Zombie 会被瞬间消灭，而该 Zombie 没有时间进行任何攻击操作。因此，即便 Zombie 进入了一个 Plant 所在的位置，但该位置属于其他植物的攻击位置集合，则 Zombie 会被瞬间消灭而所在位置的植物则安然无恙（在我们的设定中，Plant 的攻击位置不包含自身所在位置，否则你就不可能击溃它了）。
Zombies 的目标是对 Plants 的阵地发起进攻并获得最大的能源收入。每一次，你可以选择一个可进攻的植物进行攻击。本题的目标为，制定一套 Zombies 的进攻方案，选择进攻哪些植物以及进攻的顺序，从而获得最大的能源收入。
思路
最大权闭合子图模板题。
发现如果要吃掉 ((i,j)) 的植物有两个限制：((i,j+1)) 被吃掉，且所有保护 ((i,j)) 的植物全部被吃掉。
如果位置 ((i,j)) 的植物价值非负，那么我们从源点向它连一条边；否则将他向汇点连一条边，流量均为其价值的绝对值。
然后考虑上述两种限制：显然如果 ((x_1,y_1)) 限制了 ((x_2,y_2))，我们可以从 ((x_2,y_2)) 向 ((x_1,y_1)) 连一条流量为 (+infty) 的边。这样最大权闭合子图的模型就建立了。
但是我们还需要考虑如果有若干植物互相保护形成了环，那么它们是一定都不可以选的，且这个环上任意植物保护的不在环上的植物都不可以选。
所以我们可以先拓扑排序求出环，将环上的点标记好，不加入网络图中即可。
注意拓扑排序需要将网络图上的边反向之后跑，因为网络图上的一条限制的边 (x o y) 指的是 (x) 被 (y) 保护。
代码
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=610,M=1000010,Inf=1e9;
int n,m,maxf,tot=1,S,T,val[35][35],deg[N],head[N],cur[N],dep[N];
vector<pair<int,int> > pro[35][35];
struct edge
{
int next,to,flow;
}e[M];
int ID(int x,int y)
{
return (x-1)*m+y;
}
void add(int from,int to,int flow)
{
e[++tot].to=to;
e[tot].flow=flow;
e[tot].next=head[from];
head[from]=tot;
}
void topsort()
{
queue<int> q;
for (int i=1;i<N;i++)
if (!deg[i]) q.push(i);
while (q.size())
{
int u=q.front(); q.pop();
for (int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
deg[v]--;
if (!deg[v]) q.push(v);
}
}
}
bool bfs()
{
memcpy(cur,head,sizeof(head));
memset(dep,0x3f3f3f3f,sizeof(dep));
queue<int> q;
q.push(S); dep[S]=0;
while (q.size())
{
int u=q.front(); q.pop();
for (int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if (e[i].flow && !deg[v] && dep[v]>Inf)
{
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[T]<Inf;
}
int dfs(int x,int flow)
{
if (x==T) return flow;
int res,used=0;
for (int i=cur[x];~i;i=e[i].next)
{
cur[x]=i;
int v=e[i].to;
if (e[i].flow && dep[v]==dep[x]+1)
{
res=dfs(v,min(e[i].flow,flow-used));
used+=res;
e[i].flow-=res; e[i^1].flow+=res;
if (used==flow) return flow;
}
}
return used;
}
void dinic()
{
while (bfs())
maxf-=dfs(S,Inf);
}
int main()
{
memset(head,-1,sizeof(head));
S=N-1; T=N-2;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1,t,x,y;j<=m;j++)
{
scanf("%d%d",&val[i][j],&t);
if (val[i][j]>=0)
{
add(ID(i,j),S,1);
deg[S]++;
}
else
{
add(T,ID(i,j),1);
deg[ID(i,j)]++;
}
if (j<m)
{
add(ID(i,j+1),ID(i,j),1);
deg[ID(i,j)]++;
}
while (t--)
{
scanf("%d%d",&x,&y);
x++; y++;
pro[i][j].push_back(mp(x,y));
add(ID(i,j),ID(x,y),1);
deg[ID(x,y)]++;
}
}
topsort();
memset(head,-1,sizeof(head));
tot=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (!deg[ID(i,j)])
{
if (val[i][j]>=0)
{
add(S,ID(i,j),val[i][j]);
add(ID(i,j),S,0);
}
else
{
add(ID(i,j),T,-val[i][j]);
add(T,ID(i,j),0);
}
if (j<m && !deg[ID(i,j+1)])
{
add(ID(i,j),ID(i,j+1),Inf);
add(ID(i,j+1),ID(i,j),0);
}
for (int k=0;k<pro[i][j].size();k++)
{
int x=pro[i][j][k].first,y=pro[i][j][k].second;
add(ID(x,y),ID(i,j),Inf);
add(ID(i,j),ID(x,y),0);
}
}
dinic();
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (!deg[ID(i,j)] && val[i][j]>0) maxf+=val[i][j];
printf("%d",maxf);
return 0;
}