P8604 [蓝桥杯 2013 国 C] 危险系数 题解

· · 题解

说句闲话，《地道战》似乎是我小学时语文老师喊我们看过的电影。

好了，现在进入正题。

1.题目大意:

给你 n 个点，m 条边。注意：这里是双向边。 再给定起点和终点，求从起点到终点必须经过点的个数。

2.分析：

这道题的 n 和 m 都很小，可以用深搜做。

首先，深搜的变量有两个：x 表示当前所在的结点编号； cnt 表示从起点到 x，这是走的第几步。所以，递归调用就出来了：

dfs(sx/*这是起点*/,0);

我们用 flag[] 表示当前这个点是否走过，防止无穷递归。接下来，我们设一个 a[]，表示当前这一步是哪个点。这样，深搜框架就搭好了：

void dfs(int x,int cnt){
    a[cnt]=x;
    flag[x]=1;
    if(x==ex){//到达终点，返回
        ……
        return;
    }
    int l=g[x].size();//vector存图
    for(int i=0;i<l;i++){
        int y=g[x][i];
        if(!flag[y]){//如果这个点没走过就走
            dfs(y,cnt+1);
        }
    }
    a[cnt]=0;
    flag[x]=0;//回溯
}

现在，有同学就发现，返回这里省略了。哦，我们答案没法输出啊。

我们可以这么办：对于每种到达终点的路线，每一步都对应唯一的点。如果所有的路线都经过了一个点，说明这个点一定得走到。

于是，省略的部分出来了：

s++;
for(int i=0;i<=cnt;i++){
    t[a[i]]++;
}
a[cnt]=0;
flag[x]=0;

这里的 s 表示方案总数，t[] 表示对于每个点，它在多少种方案里。

注意两点：这里的 i 从 0 开始，因为深搜最开始存就是从 a_0 开始的；其次就是循环完也还要回溯，不然就永远到不了终点了（因为终点打上标记了）。

最后的输出就很简单了：

for(int i=1;i<=n;i++){
    if(t[i]==s){
        ans++;
    }
}
cout<<ans-2;

只需注意一点：由于起点和终点不算，所以 ans 要减 2。

完整代码就不给啦，记得加双向边哦~