Beyond the Void
BYVoid
NOI 2009 植物大战僵尸

问题简述

有一些植物,每个植物携带有一定的资源(可正可负),且有一个攻击范围,可以保护攻击位置上的另一个植物。有一群僵尸从右向左进攻植物,僵尸不能走到植物的攻击范围内。任务是求一个进攻方案,使得僵尸获得的资源尽可能多。

问题建模

首先我们我建立图论模型,把每个植物当做一个顶点,植物携带的资源数目为顶点的权值。如果一个植物b在另一个植物a的攻击范围内,连接一条有向边<a,b>,表示a可以保护b。由于僵尸从右向左进攻,可以认为每个植物都被它右边相邻的植物保护,对于每个植物a(除最左边一列),向其左边的相邻植物b,连接一条有向边<a,b>。

题目中给出的样例建图后如下所示

image

观察上图发现,{5,6}互相依赖,不可能被攻击到。我们可以用拓扑排序去除图中的环依赖结构,以简化图。

image

解法1 搜索

算法描述
建模后,直接观察发现可以搜索。每次寻找一个入度为0的顶点,尝试攻击它,更新它指向的点的入度继续搜索。搜索中记录选取的顶点的权值之和,保留最大值。

image

复杂度分析
搜索的时间复杂度为O(MN)。在实际测试中得到40分。
参考程序
```cpp /* * Problem: NOI2009 pvz * Author: Guo Jiabao * Time: 2009.7.29 12:01 * State: Solved * Memo: 暴力搜索 */ #include #include #include #include #include

using namespace std;

const int MAXN=603,MAXM=MAXNMAXN4,INF=~0U»1;

struct edge { edge *next; int t; }*V[MAXN],ES[MAXM];

FILE *fi,*fo;

int R,C,EC,Ans,Maxflow,Stop,S,T,N; int score[MAXN],ind[MAXN]; bool vis[MAXN];

inline void addedge(int a,int b) { ES[++EC].next = V[a]; V[a] = ES+EC; V[a]->t = b; }

inline int point2id(int x,int y) { return x * C + y + 1; }

void init() { int i,j,k,l,q,x,y,s,c; fi = fopen(“pvz.in”,“r”); fo = fopen(“pvz.out”,“w”); fscanf(fi,"%d%d",&R,&C); for (i=0;i<R;i++) { for (j=0;j<C;j++) { k = point2id(i,j); if (j+1<C) { q = point2id(i,j+1); addedge(q,k); ind[k]++; } fscanf(fi,"%d%d",&s,&c); score[k] = s; for (l=1;l<=c;l++) { fscanf(fi,"%d%d",&x,&y); q = point2id(x,y); addedge(k,q); ind[q]++; } } } N=R*C; }

void dfs(int s) { if (s > Ans) Ans = s; int i; edge *e; for (i=1;i<=N;i++) if (ind[i] == 0 && !vis[i]) { vis[i]=true; for (e=V[i];e;e=e->next) ind[ e->t ]–; dfs(s+score[i]); vis[i]=false; for (e=V[i];e;e=e->next) ind[ e->t ]++; } }

void solve() { Ans = 0; dfs(0); fprintf(fo,"%d\n",Ans); fclose(fi); fclose(fo); }

int main() { init(); solve(); return 0; }


<h4><a name="_Toc241653483">解法</a>2 最大封闭子图</h4>

<h5><a name="_Toc241653484">算法描述</a></h5>
将图转置后发现,一个合法的攻击方案是一个<strong>封闭子图</strong>(Closure of a Graph),我们的目标就是最大化攻击方案的点权值和,就是要求一个<strong>最大封闭子图</strong>(Maximum Weight Closure of a Graph),只需转化为网络流模型,即可解决。
<h5><a name="_Toc241653485">算法分析</a></h5>
样例的图转置后如下,其最大封闭子图为{1,2,4}。

<a href="https://byvoid.com/attachments/wp/2010/01/image8.png"><img title="image" src="https://byvoid.com/attachments/wp/2010/01/image8.png" alt="image" width="175" height="166" /></a>

最大封闭子图的玩网络流建模方法为:

1. 建立附加源S和附加汇T。

2. 图中原有的边容量设为∞。

3. 从S向每个权值为正的点连接一条容量为该点权值的有向边。

4. 从每个权值不为正的点向T连接一条容量为该点权值绝对值的有向边。

在网络上求S到T的网络最大流Maxflow,最大封闭子图的权值就是(所有正权点权值之和 – Maxflow)。

样例建模后如下图所示,求得Maxflow = 5,所以最大封闭子图的权值为(10 + 20 – 5) = 25。

<a href="https://byvoid.com/attachments/wp/2010/01/image9.png"><img title="image" src="https://byvoid.com/attachments/wp/2010/01/image9.png" alt="image" width="175" height="404" /></a>

求最大封闭子图的网络流建模方法的严格证明见胡伯涛《最小割模型在信息学竞赛中的应用》。
<h5><a name="_Toc241653486">复杂度分析</a></h5>
该图点数为O(NM),边数可达O(N<sup>2</sup>M<sup>2</sup>)。拓扑排序和建图的时间为O(N<sup>2</sup>M<sup>2</sup>),用Dinic算法求网络最大流的时间为O(|V|<sup>2</sup>|E|),所以总时间复杂度为O(N<sup>4</sup>M<sup>4</sup>)。在实际测试中通过了所以测试点,得到100分。
<h5><a name="_Toc241653487">参考程序</a></h5>
```cpp
/*
* Problem: NOI2009 pvz
* Author: Guo Jiabao
* Time: 2009.7.29 11:52
* State: Solved
* Memo: 最大封闭子图 网络最大流
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN=603,MAXM=MAXN*MAXN*4,INF=~0U>>1;

struct edge
{
	edge *next,*op;
	int t,c;
}*V[MAXN],*V0[MAXN],*P[MAXN],ES[MAXM],*Stae[MAXN];

FILE *fi,*fo;

int R,C,EC,Ans,Maxflow,Stop,S,T,N;
int score[MAXN],ind[MAXN],Lv[MAXN],Stap[MAXN],Q[MAXN];
bool ts[MAXN];

inline void addedge(edge **V,int a,int b,int c)
{
	ES[++EC].next = V[a]; V[a] = ES+EC; V[a]->t = b; V[a]->c=c;
	ES[++EC].next = V[b]; V[b] = ES+EC; V[b]->t = a; V[b]->c=0;
	V[a]->op = V[b]; V[b]->op = V[a];
}

inline int point2id(int x,int y)
{
	return x * C + y + 1;
}

void init()
{
	int i,j,k,l,q,x,y,s,c;
	fi = fopen("pvz.in","r");
	fo = fopen("pvz.out","w");
	fscanf(fi,"%d%d",&R,&C);
	for (i=0;i<R;i++)
	{
		for (j=0;j<C;j++)
		{
			k = point2id(i,j);
			if (j+1<C)
			{
				q = point2id(i,j+1);
				addedge(V0,q,k,1);
				ind[k]++;
			}
			fscanf(fi,"%d%d",&s,&c);
			score[k] = s;
			for (l=1;l<=c;l++)
			{
				fscanf(fi,"%d%d",&x,&y);
				q = point2id(x,y);
				addedge(V0,k,q,1);
				ind[q]++;
			}
		}
	}
	N=R*C;
}

void topsort()
{
	int i,j;
	Stop = 0;
	for (i=1;i<=N;i++)
		if (ind[i]==0)
			Stap[++Stop] = i;
	while (Stop)
	{
		i = Stap[Stop--];
		ts[i] = true;
		for (edge *e=V0[i];e;e=e->next)
		{
			j=e->t;
			if (e->c)
			{
				ind[j]--;
				if (ind[j] == 0)
					Stap[++Stop] = j;
			}
		}
	}
}

void makegraph()
{
	int i,j;
	S=0;
	T=N+1;
	for (i=1;i<=N;i++)
		if (ts[i])
		{
			if (score[i] > 0)
			{
				addedge(V,S,i,score[i]);
				Ans += score[i];
			}
			else
				addedge(V,i,T,-score[i]);
			for (edge *e=V0[i];e;e=e->next)
			{
				j=e->t;
				if (ts[j] && e->c)
				{
					addedge(V,j,i,INF);
				}
			}
		}
}

bool Dinic_label()
{
	int i,j,head,tail;
	memset(Lv,0,sizeof(Lv));
	Q[head=tail=0] = S;
	Lv[S] = 1;
	while (head<=tail)
	{
		i = Q[head++];
		for (edge *e=V[i];e;e=e->next)
		{
			j = e->t;
			if (Lv[j] == 0 && e->c)
			{
				Lv[j] = Lv[i]+1;
				if (j==T)
					return true;
				Q[++tail] = j;
			}
		}
	}
	return false;
}

void Dinic_aug()
{
	int i,j,delta;
	for (i=S;i<=T;i++)
		P[i] = V[i];
	Stap[Stop=1]=S;
	while (Stop)
	{
		i = Stap[Stop];
		if (i!=T)
		{
			for (;P[i];P[i]=P[i]->next)
				if (P[i]->c && Lv[ j = P[i]->t ] == Lv[i] + 1)
					break;
			if (P[i])
			{
				Stap[++Stop] = j;
				Stae[Stop] = P[i];
			}
			else
				Stop--,Lv[i] = 0;
		}
		else
		{
			delta = INF;
			for (i=Stop;i>=2;i--)
				if (Stae[i]->c < delta)
					delta = Stae[i]->c;
			for (i=Stop;i>=2;i--)
			{
				Stae[i]->c -= delta;
				Stae[i]->op->c += delta;
				if (Stae[i]->c == 0)
					Stop = i-1;
			}
			Maxflow += delta;
		}
	}
}

void Dinic()
{
	while (Dinic_label())
		Dinic_aug();
}

void solve()
{
	topsort();
	makegraph();
	Dinic();
	Ans -= Maxflow;
	fprintf(fo,"%d\n",Ans);
	fclose(fi);
	fclose(fo);
}

int main()
{
	init();
	solve();
	return 0;
}

上次修改时间 2017-05-26

相关日志