「BZOJ1565」[NOI2009]植物大战僵尸

problem

Description

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的进攻方案，选择进攻哪些植物以及进攻的顺序，从而获得最大的能源收入。

Input

第一行包含两个整数N, M，分别表示地图的行数和列数。

接下来N×M行描述每个位置上植物的信息。第r×M + c + 1行按照如下格式给出植物Pr, c的信息：第一个整数为Score[Pr, c], 第二个整数为集合Attack[Pr, c]中的位置个数w，接下来w个位置信息（r’, c’），表示Pr, c可以攻击位置第r’ 行第c’ 列。

Output

仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。

Sample Input

1
2
3
4
5
6
7
3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0

Sample Output

1
2
3
4
5
25
//在样例中, 植物P1,1可以攻击位置(0,0), P2, 0可以攻击位置(2,1)。 
//一个方案为，首先进攻P1,1, P0,1，此时可以攻击P0,0 。
//共得到能源收益为(-5)+20+10 = 25。
//注意, 位置(2,1)被植物P2,0保护，所以无法攻击第2行中的任何植物。

Solution

依旧是一个最大权闭合子图模型

要选中左侧的植物，就必须要选中右侧的植物，连边

要选中被保护的植物，就要选中保护该植物的植物，连边

原关系图上是可能会有环的，显然在环上的点都不能被选中
这脏比怎么这么菜连蹦极僵尸都没有

因此我们在转化为网络流图前，需要跑一边Tarjan找环

然后就可以愉快地dinic了

Code

又长又臭的代码，慎读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#define maxn 25
#define maxm 35
using namespace std;
typedef long long ll;

template <typename T>void read(T &t)
{
	t=0;char c=getchar();int f=0;
	while(!isdigit(c)){f|=c=='-';c=getchar();}
	while(isdigit(c)){t=t*10+c-'0';c=getchar();}
	if(f)t=-t;
}

const int inf=0x3f3f3f3f;
int n,m;
int s,t,ans;
int p[maxn*maxm];

struct edge
{
	int u,v,w,nxt;
}g[maxn*maxn*maxm*maxm];

int head[maxn*maxm],ecnt=1;
void eADD(int u,int v,int w)
{
	g[++ecnt].u=u;
	g[ecnt].v=v;
	g[ecnt].w=w;
	g[ecnt].nxt=head[u];
	head[u]=ecnt;
}

int dep[maxn*maxm];
bool BFS()
{
	queue<int> q;
	memset(dep,0,sizeof(dep));
	dep[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(register int i=head[u];i;i=g[i].nxt)
		{
			int v=g[i].v;
			if(dep[v] || !g[i].w)
				continue;
			dep[v]=dep[u]+1;
			if(v==t)
				return true;
			q.push(v);
		}
	}
	return false;
}

int dfs(int u,int infl)
{
	if(u==t)
		return infl;
	int rest=infl;
	for(register int i=head[u];i && rest;i=g[i].nxt)
	{
		int v=g[i].v;
		if(dep[v]!=dep[u]+1 || !g[i].w)
			continue;
		int flow=dfs(v,min(rest,g[i].w));
		if(!flow)
		{
			dep[v]=-1;
			continue;
		}
		rest-=flow;
		g[i].w-=flow;
		g[i^1].w+=flow;
	}
	return infl-rest;
}

inline int trans(int r,int c)
{
	return r*m+c;
}

int dfn[maxn*maxm],low[maxn*maxm],sign;
int stk[maxn*maxm],top,ins[maxn*maxm];
int inr[maxn*maxm];
void Tarjan(int u)
{
	dfn[u]=low[u]=++sign;
	stk[++top]=u;
	ins[u]=1;
	for(register int i=head[u];i;i=g[i].nxt)
	{
		if(!g[i].w)
			continue;
		int v=g[i].v;
		if(!dfn[v])
		{
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(ins[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		bool flag=false;
		while(stk[top]!=u)
		{
			inr[stk[top]]=1;
			flag=true;
			ins[stk[top--]]=0;
		}
		inr[stk[top]]=flag;
		ins[stk[top--]]=0;
	}
}

int main()
{
	read(n),read(m);
	for(register int i=0;i<n;++i)
		for(register int j=0;j<m;++j)
		{
			read(p[trans(i,j)]);
			int d;
			read(d);
			for(register int k=1;k<=d;++k)
			{
				int x,y;
				read(x),read(y);
				eADD(trans(x,y),trans(i,j),inf);
				eADD(trans(i,j),trans(x,y),0);
			}
		}
	for(register int i=0;i<n;++i)
		for(register int j=1;j<m;++j)
		{
			eADD(trans(i,j-1),trans(i,j),inf);
			eADD(trans(i,j),trans(i,j-1),0);
		}
	for(register int i=0;i<n;++i)
		for(register int j=0;j<m;++j)
			if(!dfn[trans(i,j)])
				Tarjan((trans(i,j)));
	s=n*m+1,t=n*m+2;
	for(register int i=0;i<n;++i)
		for(register int j=0;j<m;++j)
			if(!inr[trans(i,j)])
			{
				if(p[trans(i,j)]>=0)
					eADD(s,trans(i,j),p[trans(i,j)]),eADD(trans(i,j),s,0),ans+=p[trans(i,j)];
				else
					eADD(trans(i,j),t,-p[trans(i,j)]),eADD(t,trans(i,j),0);
			}
	while(BFS())
		ans-=dfs(s,inf);
	printf("%d",ans);
	return 0;
}