描述：
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=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<stations;i++)
{
del[path[i]]=true;
//先标记为摧毁
int step=dfs(total+1,range);
//此处的step表示需要删除车站的数量。
min=min<step?min:step;
del[path[i]]=false;
//取消标记
}
return min;
}
int solve()
{
for(int i=1;i<=n-2;i++)
//先检有无可疑只摧毁1个车站的方案，再检查有无摧只毁2个车站的方案，逐步加深。
{
int res=dfs(0,i);
if(res<=i)
return res;
}
}
int main()
{
while(scanf("%d%d%d",&n,&m,&k))
{
init();
if(n==0&&m==0&&k==0)
break;
for(int i=0,s,f;i<m;i++)
{
scanf("%d%d",&s,&f);
if(!mark[s][f])
{
mark[s][f]=true;
map[s].push_back(f);
}
}
printf("%d\n",solve());
}
}