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
```
如下图

相关日志