hdu 2181(哈密尔顿环）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2181

题意：就是让你求哈密尔顿环，并输出所有可能的路径。

思路：用一个数组path[N]来保存路径，然后暴搜就可以了，不过回退的时候，visited[i]应该置为0。

View Code

 1 #include<iostream>
 2 const int N=20;
 3 using namespace std;
 4 int map[N+1][N+1];
 5 int visited[N+1];
 6 int path[N+1];
 7 int m,_count=1;
 8 
 9 void Initiate(){
10     int x;
11     memset(map,0,sizeof(map));
12     for(int i=1;i<=20;i++){
13         for(int j=1;j<=3;j++){
14             scanf("%d",&x);
15             map[i][x]=1;
16         }
17     }
18 }
19 
20 void print(){
21     printf("%d:  ",_count++);
22     for(int i=1;i<=20;i++){
23         printf("%d ",path[i]);
24     }
25     printf("%d\n",m);
26 }
27 
28 
29 
30 //now为当前的城市，num为已经走过的城市的个数
31 void dfs(int now,int num){
32     visited[now]=1;
33     path[num]=now;
34     if(num==N){
35         //形成哈密尔顿环
36         if(map[now][m]){
37             print();
38         }
39     }else {
40         for(int i=1;i<=N;i++){
41             if(!visited[i]&&map[now][i]){
42                 dfs(i,num+1);
43             }
44         }
45     }
46     visited[now]=0;//如果不存在路时要恢复
47 }
48     
49 
50 
51 int main(){
52     Initiate();
53     while(~scanf("%d",&m)&&m){
54         memset(visited,0,sizeof(visited));
55         _count=1;
56         dfs(m,1);
57     }
58     return 1;
59 }