uva 208 - Firetruck

点击打开链接

题目意思：   有一个城市发生了火灾，现在给定一个目标节点，然后给定一序列节点间的关系，然后每一次都从节点1开始，问我们从节点1到目标节点共有几条路径，并且最后打印出这些路径。

解题思路：    分序一下复杂度，对于最多有21个节点的解空间树来说，对于这颗树的每一层就是21种情况，最坏的情况是搜索到叶子节点，那么这个时候的时间复杂度是非常大，直接回溯肯定是TLE的，那么我们想到了剪枝，我们知道能够到达目标节点的节点都肯定和目标节点有关联或间接关联，那么我们只要找出这些节点，然后在这些节点里面搜索即可

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 22;

int n  , sum , flag;
int G[MAXN][MAXN];//邻接矩阵
int ans[MAXN][MAXN];//记录路径
int vis[MAXN];//标记数组
int mark[MAXN];//存储哪些节点和目标有关联
int tempG[MAXN][MAXN];

//预处理(只有那些和目标节点有关联或间接关联的点才去搜索，那么我们用mark数组将这些点标记为1)
inline void judge(int k){
    mark[k] = 1;
    for(int i = 1 ; i < MAXN ; i++){
        if(tempG[k][i] && mark[i] == 0){
            tempG[k][i] = 0;
            judge(i);
        }
    }
}

//输出函数
inline void output(){    
    for(int i = 0 ; i < sum ; i++){
        printf("%d" , ans[i][0]);
        for(int j  = 1 ; j < MAXN ; j++){
            if(ans[i][j])
               printf(" %d" , ans[i][j]);
        }
        printf("\n");
    }
    printf("There are %d routes from the firestation to streetcorner %d.\n" , sum , n);
}
//递归搜索
void dfs(int k){
    if(k == n){ //找到目标节点后就是存储路径，注意是要顺序的存储，因此还要处理一下走的步骤
        int t = 0;
        int tempsum = 0;
        for(int i = 1 ; i < MAXN ; i++){
            if(vis[i])
                tempsum++;
        }
        for(int j = 1 ; j <= tempsum ; j++){
           for(int i = 1 ; i < MAXN ; i++){
               if(vis[i] == j)
                 ans[flag][t++] = i; 
           }
        }
        ++sum;//路径加加
        ++flag;
        return;
    }
    else{
        for(int i = 2 ; i < MAXN ; i++){
            if(mark[i] && G[k][i] && vis[i] == 0){//如果节点和目标节点有关联
                vis[i] = vis[k] + 1;//这里是个技巧，方便找到走了几步
                dfs(i);
                vis[i] = 0;
            }
        }
    }
}
//主函数
int main(){
    int x  , y;
    int cnt = 1;
    while(~scanf("%d" , &n)){
        memset(vis , 0 , sizeof(vis));
        memset(G , 0 , sizeof(G));
        memset(ans , 0 , sizeof(ans));
        memset(mark , 0 , sizeof(mark));
        sum = 0;
        flag = 0;
        while(1){
            scanf("%d%d" , &x , &y);
            if(x == 0 && y == 0)
                break;
            G[x][y] = 1;//邻接矩阵
            G[y][x] = 1;
        }
        memcpy(tempG , G , sizeof(G));
        judge(n);//预处理传入目标节点的值
        vis[1] = 1;
        dfs(1);
        printf("CASE %d:\n" , cnt);
        output();
        cnt++;
    }
    return 0;
}