UVA 208 Firetruck 消防车（回溯 + 剪枝）

迷南。 2024-02-17 19:12 10阅读 0赞

题意：一个包含<=20个结点的无向图，输入一个结点k，求从1到的k的所有路径，要求字典序输出，并且结点不能重复。

思路：刚开始直接回溯，结果超时了；从终点出发，找到所有与终点连通的结点，存储在数组aa当中，之后排序（字典序输出嘛），这样的话当从起点无法到达终点时，减少了很多结点判断（剪枝）。想象一下当一个长度为20的路径>10的时候有断点，那么从起始位置1开始，肯定没有与g\[1\]\[i\]相连的路径，很快就退出dfs了。

AC代码如下：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=20+2;
    int g[maxn][maxn];       //储存无向图 
    int vis[maxn],aa[maxn];  //aa用于存储与目标点k联通的点集 
    int path[maxn];  //输出路径保存 （下标从1开始） 
    int k,total;
    int maxn2;
    void print(int tmp){
    	printf("%d",path[1]);
    	for(int i=2;i<=tmp;i++)
    	printf(" %d",path[i]);
    	printf("\n");
    }
    void dfs1(int cur){    //收集与目标点k联通的点集 
    	vis[cur]=1;
    	aa[maxn2++]=cur;
    	for(int i=1;i<=20;i++){
    		if(!vis[i] && g[cur][i])
    		dfs1(i);
    	}
    }
    void dfs(int cur,int tmp){   
    	if(cur==k){
    		print(tmp-1);
    		total++;
    		return ;
    	}
    	for(int i=0;i<=maxn2;i++){
    		if(g[cur][aa[i]] && !vis[aa[i]]){
    			vis[aa[i]]=1;
    			path[tmp]=aa[i];
    			dfs(aa[i],tmp+1);
    			vis[aa[i]]=0;
    		}
    	}
    }
    int main(){
    	int count1=0;
    	while(scanf("%d",&k)==1){
    		memset(g,0,sizeof(g));
    		memset(vis,0,sizeof(vis));
    		int a,b;
    		while(scanf("%d%d",&a,&b)==2 && a){
    			g[a][b]=1;
    			g[b][a]=1;
    	   }
    	   maxn2=total=0;
    	   dfs1(k);
    	   sort(aa,aa+maxn2);  //必须排序，题目要求字典序输出 
    	   memset(vis,0,sizeof(vis));
    	   printf("CASE %d:\n",++count1);
    	   path[1]=vis[1]=1;
    	   dfs(1,2);
    	   printf("There are %d routes from the firestation to streetcorner %d.\n",total,k);
    	}
    	return 0;
    }