Beyond the Void
BYVoid
POI 1998 追趕 Chase
本文正體字版由OpenCC轉換

這道題的解決方法隱藏得很深,不經過嚴密的數學推理分析是很難想到正確方法的。

注意到題上的一個看似無關緊要的條件,“不包括三角形”,這是一個突破口。由這個條件,我們可以證明,如果一個圖不存在度數爲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

相關日誌