[POJ][3291][搜索] Destroying the bus stations

描述：

Gabiluso是他国家最厉害的间谍之一。现在他试图去完成一个“不可能”的任务-减缓Colugu市的军队抵达机场的速度。Colugu市有n个车站和m条路。每条路直接连接两个车站，所有的路都是单向的。为了维护空气质量，政府停用了所有军队车辆。所以军队必须乘坐巴士去机场。两个车站之间可能不只一条路。如果一个车站被摧毁，那么所有通向那个车站的道路都没用了。Gabiluso需要去做的是摧毁一些车站使得军队不能在k分钟内赶到机场。一辆巴士通过一条路只需要一分钟。从1到n给所有车站编号。编号为1的车站在军营里，编号为n的车站在机场里。军队总是从编号为1的车站出发。

由于有重兵把守，所以编号为1和n的车站不能被摧毁。当然那里没有一条路直接从1号车站连接到n号车站。

请帮助Gabiluso计算他需要摧毁车站的最小数量，他必须完成任务。

输入：

有多组测试数据。当输入三个0时，输入停止。

对于每组测试数据：

第一行包含三个整数，n，m 和 k。 (0 < n <= 50,0 < m <= 4000, 0 < k < 1000)

紧接着有m行，每行包含两个整数 s 和 f，意思是有一条路从s号车站通往f号车站。

输出：

对于每组测试数据，输出 Gabiluso 必须摧毁车站的最小数量。

思路：

按照本题作者陈峰宏的说法，此题拥有网络流的解法，但对于这种数据范围，直接搜索即可。

本题思路部分源于《ACM 国际大学生程序设计竞赛亚洲区预选赛真题题解》，源自于作者但未高于作者。很大一部分原因是书中代码的排版方式有着非人类的可读性，所以严格意义上来说我只看懂了一部分。

下面代码的大体思路是这样的：利用深搜遍历各种车站删除方案，但并不是盲目的搜，而是在1号到n号车站的最短路径上搜索，不断摧毁最短路径上的车站。

最短路径和最短路径的长度由一个广搜来完成。其中包含一个剪枝操作，当路径长度大于k时，直接返回当前值即可。因为我们只需要关心当前路径是否大于k，而不需要具体知道大于k多少。

另外深搜也是逐步递进的，先看看只摧毁1个车站的情况下是否可行，不可行再搜只摧毁2个车站的方案，以此类推。书中作者的原话：“虽然这样看似重复搜索了很多遍，但实际上搜索的深度是有限的，因此搜索的总范围不会非常大。”

代码：

#include
#include
#include
using namespace std;
#define MAXN 50
vectormap[MAXN+1];
//邻接表 
bool del[MAXN+1],mark[MAXN+1][MAXN+1];
//del[]用于记录某个车站是否被删除 
//题目中说明了两个车站之间可以由多条路相连，但也说明了若一个车站被摧毁，那么连接它的路就没有用了。
//因此，多余的路没有用，我们需要用mark[][]记录一条边是否已经输入。如已被输入，便不再加入到邻接表中。 
int n,m,k;
//n个车站，m条路，k分钟 
struct point
//将队列元素封转在结构体中 
{
    int num;
    //车站编号 
    int pre;
    //父节点在队列中的位置
}queue[MAXN+1];
void init()
//初始化 
{
    for(int i=1;i<=MAXN;i++)
    {
        for(int j=1;j<=MAXN;j++)
            mark[i][j]=false;
        map[i].clear();
        del[i]=false;
    }
}
void make_path(int path[],point end,int& stations)
//利用end回溯并在path[]里记录下1号车站到n号车站之间的路径。 
{
    stations=0;
    while(end.pre!=1)
    {
        end=queue[end.pre];
        path[stations++]=end.num;
    }
}
int bfs(int path[],int& stations)
//计算从1号车站到2号车站的最短路径 
{
    bool visit[MAXN+1];
    //是否访问过 
    for(int i=1;i<=MAXN;i++)
        visit[i]=false;
    int step=0,head=1,tail=1;
    //step从1号车站到n号车站的最短距离。
    //now队列头元素所在位置。
    //tail队列尾部元素所在位置。 
    queue[tail++].num=1;
    visit[1]=true;
    while(tail-head)
    {
        int size=tail-head;
        while(size--)
        {
            int front=queue[head].num;
            if(front==n)
            {
                make_path(path,queue[head],stations);
                return step;
            }
            for(int i=map[front].size()-1;i>=0;i--)
            {
                int u=map[front][i];
                if(!visit[u]&&!del[u])
                {
                    visit[u]=true;
                    queue[tail].num=u;
                    queue[tail++].pre=head;
                }
            }
            head++;
        }
        step++;
        if(step>k)
        //我们只需要知道距离是否大于k即可，不需要知道具体大多少。 
            return step;
    }
    return k+1;
    //1号车站无法通往n号车站。返回一个大于k的值即可。 
}
int dfs(int total,int range)
//total表示已经摧毁车站的数量。 
//range表示准许摧毁车站的数量。 
{
    if(total>range)
        return MAXN;
    int path[MAXN+1],stations;
    //path[]用于记录当前状态下的最短路径。
    //stations表示最短路径中除1号车站和n号车站外的车站数量。 
    if(bfs(path,stations)>k)
            return total;
    int min=MAXN;
    //记录最少摧毁车站的数量。 
    for(int i=0;i