POI 2000 Skiers 滑雪隊

看過這道題，很容易想到用網絡流的方法來構建問題模型。但是N<=5000，沒有給出明確的邊數限制使得我們不能從網絡流下手。重新讀題，注意到每個點鄰接到的點都是按照一個順序（自東向西）給出的，而且邊不會有交叉，這就是解決問題的突破口。

我們採用貪心的策略，每次儘量靠東地深度優先搜索一條到目標的路徑，把這條路徑上的點都標記爲使用過，然後在剩餘的頂點構成的圖中再次儘量靠東地深度優先搜索一條到目標的路徑，直到不能到達目標位置，統計搜索到的路徑。

這種貪心策略爲什麼是正確的？假設圖中有M條到達目標的路徑，分別爲P1,P2,P3...PM，而且Pi在Pi+1的東邊。因爲所有路徑都是不相交的，所以Pi上的所有頂點也一定在Pi+1上所有頂點的東邊。由此可以得出，我們每次儘量靠東搜索，給剩餘的路徑留下儘量多的位置，才能是路徑的條數最大。

時間複雜度爲O(N+E)，N爲頂點數，E爲邊數。另外因爲沒有給出E的數目限制，而N<=5000，我們只好使用動態開闢的鄰接鏈表的方法來儲存這個圖。

/* 
 * Problem: POI2000 nar
 * Author: Guo Jiabao
 * Time: 2008.12.22 13:23
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

struct edge
{
    int t;
    edge *next;
};

struct adjl
{
    edge *f,*l;
};

const int MAX=5001;

int N,Ans;
adjl A[MAX];
bool Nuked[MAX];

void addedge(int a,int b)
{
    if (A[a].f)
        A[a].l=A[a].l->next=new edge;
    else
        A[a].f=A[a].l=new edge;
    A[a].l->t=b;
    A[a].l->next=0;
}

void init()
{
    int i,j,M,t;
    freopen("nar.in","r",stdin);
    freopen("nar.out","w",stdout);
    scanf("%d",&N);
    for (i=1;i<=N;i++)
    {
        scanf("%d",&M);
        for (j=1;j<=M;j++)
        {
            scanf("%d",&t);
            addedge(i,t);
        }
    }
}

bool dfs(int i)
{
    if (i==N)
        return true;
    Nuked[i]=true;
    for (edge *k=A[i].f;k;k=k->next)
    {
        if (!Nuked[k->t] && dfs(k->t))
            return true;
    }
    return false;
}

void solve()
{
    for (edge *k=A[1].f;k;k=k->next)
        if (!Nuked[k->t] && dfs(k->t))
            Ans++;
}

int main()
{
    init();
    solve();
    printf("%d",Ans);
    return 0;
}

<h2><span class="mw-headline">滑雪隊 </span></h2>

一個滑雪隊在Byte山上組織了一次訓練。山的北坡有一個滑雪場，所有的滑雪者都要從山上的起點站滑到山下的終點站。此次訓練中各隊員同時出發到終點站會合，除了始末兩處外，隊員們的滑雪路徑不能相交，且山上的滑雪道只能從上往下滑。

滑雪道的分佈地圖由多塊被林地連接的空地組成，每塊空地都處於不同的高度。兩塊空地間至多由一塊林地連接。滑雪過程中，滑雪者可以選擇路徑訪問任一空地（但不必全部經過）。各滑雪道只在空地相會，既不穿隧道，也不臨空飛越。

任務：

編寫一個程序完成下列工作：

讀入滑雪場的地圖；
算出能參加訓練的最大隊員數；
把結果寫入文件。

輸入：

文件的第一行是空地的數目n，2≤n≤5000。以下n-1行，每行都有一些用空格分開的整數，第(i+1)行的數字描述的是從空地i沿林地往下可到達的其它空地。該行第一個整數k表示這些空地的個數，以下k個整數即它們的編號，按從東到西的順序排列(即通向各空地的林地的位置)。空地從1 到n編號。起點站建於空地1，終點站建於空地n。

輸出：

僅一行，包括一個整數，即能參加訓練的最大人數。

輸入樣例：
```
15
  5 3 5 9 2 4
  1 9
  2 7 5
  2 6 8
  1 7
  1 10
  2 14 11
  2 10 12
  2 13 10
  3 13 15 12
  2 14 15
  1 15
  1 15
  1 15
```
輸出樣例：
```
3
```
如下圖

相關日誌