首页 > 代码库 > HDU 2181 哈密顿绕行世界问题

HDU 2181 哈密顿绕行世界问题

 说来很惭愧 ,最近一直 在做 搜索类的题目,这类搞了好久也没搞出来0 0,可能是分析问题的能力不够强,还需要多多训练..

最后参考了高手的代码,的确值得借鉴学习的..以前也做过素数环啊,一模一样,这题咋做不出来,值得深思啊..

 1 #include<iostream> 2 using namespace std; 3 #define maxn 20 4 int matrix[maxn+1][maxn+1],arr[maxn+1]; 5 bool  visited[maxn+1]; 6 int m,count = 1; 7 void dfs(int val,int num)   //val为当前走的城市,num为已走的城市个数 8 { 9     int i;10     arr[num] = val;//标记可以走的位置11     visited[val] = true;12     if(num == maxn)13     {14         if(matrix[val][m])//地点为val的城市能回到原点15         {16             printf("%d: ",count++);17             for(i = 1; i <= maxn; i++)18                 printf(" %d",arr[i]);19             printf(" %d",m);20             printf("\n");21         }22     }23     else24     {25         for(i = 1; i <= maxn; i++)26             if(!visited[i] && matrix[val][i])27                 dfs(i,num+1);28     }29     visited[val] = false;30 }31 int main() 32 {33    // freopen("2181.txt","r",stdin);34     int i,j,a,b,c;35     memset(matrix,0,sizeof(matrix));36     for(i = 1; i <= maxn; i++)37     {38         scanf("%d%d%d",&a,&b,&c);39         matrix[i][a] = matrix[i][b] = matrix[i][c] = 1;//将该点和相连的点标记40     }41     while(scanf("%d",&m) && m)42     {43         memset(visited,false,sizeof(visited));44         dfs(m,1);45     }46     return 0;47 }

 

HDU 2181 哈密顿绕行世界问题