Beyond the Void
BYVoid
POI 2001 Ants and the ladybug 蚂蚁和瓢虫

做出这道题关键在于读懂题目,尤其是第3条和第4条规则。可以知道,所有蚂蚁是一拥而上的,而且蚂蚁很聪明,它们知道如果在某时一只蚂蚁到瓢虫的路 径与另一只蚂蚁的路径相互包含,就让距离近的蚂蚁继续行进,另一只蚂蚁停留不动。蚂蚁们还会互相礼让,如果要同时进入一个节点,就让编号小的蚂蚁进入,其 它蚂蚁停止不再动。

瓢虫会停留在多个位置,但是都是互相不关联的,我们可以把瓢虫停留的每个位置看作独立的测试点,每个测试点要用到上个测试点的结果,所以我们可以分割考虑每次瓢虫停留。

对于每次瓢虫停留,如果简单地模拟,会很容易超时。我们要把每只蚂蚁一次移动到位。首先从瓢虫的位置开始一遍BFS,找到所有可行进的蚂 蚁,记录每只蚂蚁到瓢虫位置的路径。然后按照路径长度从小到大为第一关键字,蚂蚁编号从小到大为第二关键字把蚂蚁进行排序,排名第一的蚂蚁一定是可以驱逐 瓢虫的蚂蚁,把它的路径上的顶点分别标记时间。然后依次处理每只蚂蚁,如果某只蚂蚁路径上有节点已经被标记时间,则这只蚂蚁的最大移动时间就是已经标记的 时间。在移动时也标记时间,用于影响后面的蚂蚁。这样,移动所有蚂蚁的时间复杂度是O(N+K)的。

算法的总的时间复杂度为O((N+K*logK)*L),可以很快解决问题。实际编写时有很多细节需要注意。

/* 
 * Problem: POI2001 mro
 * Author: Guo Jiabao
 * Time: 2009.2.2 21:43
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN=5001,MAXK=1001,INF=0x7FFFFFFF;

struct edge{int t;edge *next;};
struct adjl{edge *f,*l;};
struct vertex{int id,ant,label;};
struct ant{int vtx,id,dist,hits;};
struct path{path *from;int p;};

edge E[MAXN*2];
adjl A[MAXN];
vertex V[MAXN];
ant Ant[MAXK];
int PL[MAXK],Pt[MAXK][MAXN];
int N,K,L,Ec=-1,Target;
int Order[MAXK];

inline void addedge(int a,int b)
{
	if (A[a].f)
		A[a].l=A[a].l->next=&E[++Ec];
	else
		A[a].f=A[a].l=&E[++Ec];
	E[Ec].t=b;
}

void init()
{
	int i,a,b;
	freopen("mro.in","r",stdin);
	freopen("mro.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<N;i++)
	{
		scanf("%d%d",&a,&b);
		addedge(a,b);
		addedge(b,a);
	}
	for (i=1;i<=N;i++)
		V[i].id=i;
	scanf("%d",&K);
	for (i=1;i<=K;i++)
	{
		scanf("%d",&a);
		V[a].ant=i;
		Ant[i].id=i;
		Ant[i].vtx=a;
		Order[i]=i;
	}
	scanf("%d",&L);
}

void BFS()
{
	path Queue[MAXN],u,v;
	int Head=0,Tail=0;
	bool vis[MAXN];
	int *P;
	memset(vis,0,sizeof(vis));
	Queue[0].p=Target;
	Queue[0].from=0;
	vis[Target]=true;
	while (Head<=Tail)
	{
		v.from=&Queue[Head];
		u=Queue[Head++];
		for (edge *k=A[u.p].f;k;k=k->next)
		{
			v.p=k->t;
			if (!vis[v.p])
			{
				vis[v.p]=true;
				if (V[v.p].ant!=0)
				{
					int a=V[v.p].ant;
					path *b=&v;
					PL[a]=0;
					P=Pt[a];
					while (b->from)
					{
						P[++PL[a]]=b->p;
						b=b->from;
					}
					P[++PL[a]]=Target;
					Ant[a].dist=PL[a]-1;
				}
				else
					Queue[++Tail]=v;
			}
		}
	}
}

void Move()
{
	int p,i,j,u,v,MaxStep,Step;
	i=Order[1];
	Ant[i].hits++;
	MaxStep=PL[i];
	for (p=1;p<=K && Ant[i=Order[p]].dist<INF;p++)
	{
		Step=MaxStep;
		for (j=1;j<=PL[i];j++)
		{
			u=Pt[i][j];
			if (V[u].label)
			{
				Step=V[u].label+1;
				break;
			}
		}
		u=Pt[i][1];
		V[u].ant=0;
		for (j=2;j<=Step;j++)
		{
			v=Pt[i][j];
			if (V[u].label+1 > V[v].label)
				V[v].label=V[u].label+1;
			else
				break;
			u=v;
		}
		Ant[i].vtx=u;
		V[u].ant=i;
	}
}

inline int cmp(const void *a,const void *b)
{
	int A=*(int *)a,B=*(int *)b;
	if ( Ant[A].dist < Ant[B].dist ) return -1;
	if ( Ant[A].dist > Ant[B].dist ) return 1;
	if ( Ant[A].id   < Ant[B].id   ) return -1;
	return 1;
}

void clear()
{
	int i;
	for (i=1;i<=K;i++)
		Ant[i].dist=INF;
	for (i=1;i<=N;i++)
		V[i].label=0;
}

void solve()
{
	int i,a;
	for (i=1;i<=L;i++)
	{
		scanf("%d",&Target);
		if (V[Target].ant!=0)
		{
			a=V[Target].ant;
			Ant[a].hits++;
		}
		else
		{
			clear();
			BFS();
			qsort(Order+1,K,sizeof(Order[0]),cmp);
			Move();
		}
	}
	for (i=1;i<=K;i++)
	{
		printf("%d %dn",Ant[i].vtx,Ant[i].hits);
	}
}

int main()
{
	init();
	solve();
	return 0;
}
<h2><span class="mw-headline">蚂蚁和瓢虫 </span></h2>

蚂蚁和蚜虫是共生的。蚜虫分泌出蜜汁给蚂蚁引用。蚂蚁帮助蚜虫赶走它的天敌——瓢虫。在蚂蚁山附近有一个树,这里是蚜虫生活的地方。蚜虫吸取树的汁 液。有n个蚂蚁兵,用1到n编号。一个瓢虫威胁着这个文明,它经常出现在蚜虫活动的地方。当瓢虫坐在树上时,蚂蚁兵会出动把它赶走。他们按照如下的规则:

树上的任意两点之间都只有一条路径,所有的蚂蚁都沿着它所在点到瓢虫的路径前进,每移动一个位置,花的时间是单位1。
  • 如果蚂蚁和瓢虫在同一个位置,那么蚂蚁立即把它赶走。

  • 如果某个蚂蚁的路径上有另外一只蚂蚁,那么距离目标较远的蚂蚁待在原地不动,较近的那个蚂蚁继续前进。

  • 如果有多个蚂蚁要进入同一个位置,那么选择编号最小的蚂蚁,其余的蚂蚁留在原位置不动。

  • 当蚂蚁到达了瓢虫的位置以后,把它赶走,然后停留在该位置。

    瓢虫是非常顽固的动物,它被赶走了以后还会再停留到别的位置。然后蚂蚁继续行动。为了使问题简单化,我们假定从一个位置到达与它相邻的位置花1个单位的时间。

    任务:

    读入树的描述,蚂蚁的开始位置,以及瓢虫停留地点。 给出每个蚂蚁的最后的位置,以及该蚂蚁赶走瓢虫的次数。

    输入:

    文件的第一行,一个整数n,1<=n<=5000。表示地点的编号。接下来n-1行描述了树里的边,每行两个整数a和b,表示 这两点之间相连。然后一行是整数k,1<=k<=1000 and k<=n。是蚂蚁兵的数目。接下来k行,每行一个整数,表示蚂蚁兵开始的位置。没有两个蚂蚁位于一个位置。然后是一个整数l, 1<=l<=500,即瓢虫停留l次。下面的l行每行一个整数,表示瓢虫依次停留的位置。

    输出:

    k行。每行两个整数,分别表示第k个蚂蚁最后的位置以及它赶走瓢虫的次数。

    Sample Input

    4
      1 2
      1 3
      2 4
      2
      1
      2
      2
      2
      4

    Sample Output

    1 0
      4 2

    Figure

    Image:Mro.gif

上次修改时间 2017-05-22

相关日志