首页 > 代码库 > 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 哈密顿绕行世界问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。