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

相關日誌