Beyond the Void
BYVoid
POI 1998 追赶 Chase

这道题的解决方法隐藏得很深,不经过严密的数学推理分析是很难想到正确方法的。

注意到题上的一个看似无关紧要的条件,“不包括三角形”,这是一个突破口。由这个条件,我们可以证明,如果一个图不存在度数为1的顶点,B永远也追不上A。也就是B想追上A,必须让A“走投无路”。

于是我们首先把原图处理一下,求出对于A来说的安全区。对于A来说的安全区,也就是一个没有度为1的顶点的最大子图。我们把这个安全区求出,并标记上。

A要想不被B抓住,则一定要向安全区中逃跑。如果A能够在B追上A之前逃离到安全区,则B就永远也追不上A。否则,A无论如何也会被B追上。在A“必死无疑”的时候,A要想尽可能晚的被B追上,就必须想远离B的方向跑。

有了以上的分析,得出下列算法 1、求出安全区的顶点。 2、分别求出A,B初始位置开始,到每个顶点的距离,记作DA[i]和DB[i]。 3、若存在安全区中的顶点k,使得DA[k]<DB[k],则B追不上A,输出"NIE",结束。 4、如果不存在上述顶点k,则找到满足DA[i]<DB[i]时,DB[i]的最大值,输出DB[i]的最大值。

时间复杂度:O(M+N)

/* 
 * Problem: POI1998 gon
 * Author: Guo Jiabao
 * Time: 2008.12.3 18:42:14
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

class tList
{
	public:
		tList *next;
		int v;
		tList(int tv) : v(tv)
		{
			next=0;
		}
};

class tQueue
{
	public:
		tList *first,*last;
		int size;
		tQueue()
		{
			reset();
		}
		void reset()
		{
			first=last=0;
			size=0;
		}
		void ins(int v)
		{
			if (first)
				last=last->next=new tList(v);
			else
				first=last=new tList(v);
			size++;
		}
		int pop()
		{
			int rtn=first->v;
			tList *t=first;
			size--;
			first=first->next;
			delete t;
			return rtn;
		}
};

const int MAXN=3001;

int N,M,A,B,Ans;
int Sf[MAXN],Degree[MAXN];
int DA[MAXN],DB[MAXN];
tQueue adjl[MAXN],Q;

void init()
{
	int i,a,b;
	freopen("gon.in","r",stdin);
	freopen("gon.out","w",stdout);
	scanf("%d%d%d%d",&N,&M,&A,&B);
	for (i=1;i<=M;i++)
	{
		scanf("%d%d",&a,&b);
		adjl[a].ins(b);
		adjl[b].ins(a);
		Degree[a]++;
		Degree[b]++;
	}
	for (i=1;i<=N;i++)
	{
		Sf[i]=true;
		DA[i]=DB[i]=-1;
	}	
}

void safe()
{
	int i,j;
	tList *k;
	for (i=1;i<=N;i++)
	{
		if (Degree[i]==1)
		{
			Q.ins(i);
		}
	}
	while (Q.size)
	{
		i=Q.pop();
		Degree[i]=0;
		Sf[i]=false;
		for (k=adjl[i].first;k;k=k->next)
		{
			j=k->v;
			Degree[j]--;
			if (Degree[j]==1)
				Q.ins(j);
		}
	}
}

void dist()
{
	int i,j;
	tList *k;
	Q.reset();
	Q.ins(A);
	DA[A]=0;
	while (Q.size)
	{
		i=Q.pop();
		for (k=adjl[i].first;k;k=k->next)
		{
			j=k->v;
			if (DA[j]==-1)
			{
				DA[j]=DA[i]+1;
				Q.ins(j);
			}
		}
	}
	Q.reset();
	Q.ins(B);
	DB[B]=0;
	while (Q.size)
	{
		i=Q.pop();
		for (k=adjl[i].first;k;k=k->next)
		{
			j=k->v;
			if (DB[j]==-1)
			{
				DB[j]=DB[i]+1;
				Q.ins(j);
			}
		}
	}
}

void solve()
{
	int k;
	for (k=1;k<=N;k++)
	{
		if (Sf[k] && DA[k] < DB[k])
		{
			printf("NIE");
			return;
		}
		if (DA[k] < DB[k] && DB[k] > Ans)
		{
			Ans=DB[k];
		}
	}
	printf("%d",Ans);
}

int main()
{
	init();
	safe();
	dist();
	solve();
	return 0;
}
<h2><span class="mw-headline">追赶</span></h2>

“追赶”是两个人用棋盘玩的游戏。棋盘由编号由1到n的方块组成。每两个不同的方块将被得知它们是否与另一个相邻。每一个玩家都有一个由他控制的硬 币。在游戏的开始,玩家的硬币被放在固定的不同的方块中。一个回合内一个玩家可以不移动他的硬币,也可以把硬币移到一个相邻的方块里。

棋盘具有如下属性:

它不包括三角形,也就是没有任意三个不同的方块,它们两两相邻, 每一个玩家到达都能到达任意一个方块。

一个游戏由许多回合组成。在一个回合内,每一个玩家移一步。每一个回合由玩家A开始。我们说如果两个硬币在同一个方块中,那么玩家A被玩家 B赶上。问题要求,决定是否能对于给定一个硬币的初始位置,玩家B在对手独立移动的情况下都能赶上玩家A。如果这样,在两个人都玩得很好条件下, 多少回合玩家B赶上玩家A(即,玩家A尽量远离玩家B,玩家B尽可能快的赶上有些者A)。

例如

<a class="image" title="Image:Gon.png" href="http://www.ruvtex.cn/wiki/Image:Gon.png"><img src="http://www.ruvtex.cn/mw/images/9/91/Gon.png" alt="Image:Gon.png" width="208" height="172" /></a>

用图表示棋盘,相邻的方块(用圆圈表示)用边相连接. 如果在游戏的开始玩家A 和 B分别放置硬币在9和4的位置,那么在第三轮(如果两个人都玩的很好),玩家B将赶上玩家A. 如果开始玩家A 和 B分别放置硬币在8和4的位置,那么玩家B将不能赶上玩家A(如果A不出错).

任务

写一个程序:
  • 文本文件GON.IN t中描述了一个棋盘,初始状态下方块中放置硬币的编号。

  • 判断是否玩家B能赶上玩家A, 如果能,计算将有需要多少回合(如果两个玩家都玩得很好);

  • 将结果写入文本文件 GON.OUT中.

    输入

    在文件GON.IN 的第一行有4个整数n, m, a 和b,它们用单个空格分隔。2<=n<=3000, -1<=m<=15000, 1<=a,b<=n ,a <b。它们分别表示棋盘中的方块数目, 相邻的一对方块(无序)数目,玩家A的硬币放置在方块中的编号,玩家B的硬币放置在方块中的编号。下面的每一行包含两个用一个空格分开的整数,表示每一对 相邻的方块编号。

    输出

    在文本文件GON.OUT 的第一行写入如下信息:

  • 一个单词NIE ,如果玩家 B不能赶上玩家A, 或者

  • 一个整数-如果玩家B能赶上玩家A的最少游戏轮数

    输入示例

    9 11 9 4
      1 2
      3 2
      1 4
      4 7
      7 5
      5 1
      6 9
      8 5
      9 8
      5 3
      4 8

    输出示例  3


上次修改时间 2017-05-22

相关日志