哈密顿绕行世界问题 HDU – 2181

作者: qwq 分类: ACM 发布时间: 2017-03-27 23:21

这个题在写完之后提交发现是 WA,然后找了半天,也没有发现什么错误,偶然之间把编译器从G++换成C++之后就AC了。

我感觉非常奇怪,在问过大神之后才明白我之前打开了ios::sync_with_stdio(false)这个开关关闭了。关闭之后的结果就是cin和scanf混用的话会出错。

这种错误真的很难发现呀。。。要是在赛场我肯定会因此浪费好多时间。。。

一个规则的实心十二面体,它的 20个顶点标出世界著名的20个城市,你从一个城市出发经过每个城市刚好一次后回到出发的城市。

  • Input
  • 前20行的第i行有3个数,表示与第i个城市相邻的3个城市.第20行以后每行有1个数m,m<=20,m>=1.m=0退出.
  • Output
  • 输出从第m个城市出发经过每个城市1次又回到m的所有路线,如有多条路线,按字典序输出,每行1条路线.每行首先输出是第几条路线.然后个一个: 后列出经过的城市.参看Sample output
  • Sample Input
  • 2 5 20
    1 3 12
    2 4 10
    3 5 8
    1 4 6
    5 7 19
    6 8 17
    4 7 9
    8 10 16
    3 9 11
    10 12 15
    2 11 13
    12 14 20
    13 15 18
    11 14 16
    9 15 17
    7 16 18
    14 17 19
    6 18 20
    1 13 19
    5
    0
  • Sample Output
  • 1:  5 1 2 3 4 8 7 17 18 14 15 16 9 10 11 12 13 20 19 6 5
    2:  5 1 2 3 4 8 9 10 11 12 13 20 19 18 14 15 16 17 7 6 5
    3:  5 1 2 3 10 9 16 17 18 14 15 11 12 13 20 19 6 7 8 4 5
    4:  5 1 2 3 10 11 12 13 20 19 6 7 17 18 14 15 16 9 8 4 5
    5:  5 1 2 12 11 10 3 4 8 9 16 15 14 13 20 19 18 17 7 6 5
    6:  5 1 2 12 11 15 14 13 20 19 18 17 16 9 10 3 4 8 7 6 5
    7:  5 1 2 12 11 15 16 9 10 3 4 8 7 17 18 14 13 20 19 6 5
    8:  5 1 2 12 11 15 16 17 18 14 13 20 19 6 7 8 9 10 3 4 5
    9:  5 1 2 12 13 20 19 6 7 8 9 16 17 18 14 15 11 10 3 4 5
    10:  5 1 2 12 13 20 19 18 14 15 11 10 3 4 8 9 16 17 7 6 5
    11:  5 1 20 13 12 2 3 4 8 7 17 16 9 10 11 15 14 18 19 6 5
    12:  5 1 20 13 12 2 3 10 11 15 14 18 19 6 7 17 16 9 8 4 5
    13:  5 1 20 13 14 15 11 12 2 3 10 9 16 17 18 19 6 7 8 4 5
    14:  5 1 20 13 14 15 16 9 10 11 12 2 3 4 8 7 17 18 19 6 5
    15:  5 1 20 13 14 15 16 17 18 19 6 7 8 9 10 11 12 2 3 4 5
    16:  5 1 20 13 14 18 19 6 7 17 16 15 11 12 2 3 10 9 8 4 5
    17:  5 1 20 19 6 7 8 9 10 11 15 16 17 18 14 13 12 2 3 4 5
    18:  5 1 20 19 6 7 17 18 14 13 12 2 3 10 11 15 16 9 8 4 5
    19:  5 1 20 19 18 14 13 12 2 3 4 8 9 10 11 15 16 17 7 6 5
    20:  5 1 20 19 18 17 16 9 10 11 15 14 13 12 2 3 4 8 7 6 5
    21:  5 4 3 2 1 20 13 12 11 10 9 8 7 17 16 15 14 18 19 6 5
    22:  5 4 3 2 1 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5
    23:  5 4 3 2 12 11 10 9 8 7 6 19 18 17 16 15 14 13 20 1 5
    24:  5 4 3 2 12 13 14 18 17 16 15 11 10 9 8 7 6 19 20 1 5
    25:  5 4 3 10 9 8 7 6 19 20 13 14 18 17 16 15 11 12 2 1 5
    26:  5 4 3 10 9 8 7 17 16 15 11 12 2 1 20 13 14 18 19 6 5
    27:  5 4 3 10 11 12 2 1 20 13 14 15 16 9 8 7 17 18 19 6 5
    28:  5 4 3 10 11 15 14 13 12 2 1 20 19 18 17 16 9 8 7 6 5
    29:  5 4 3 10 11 15 14 18 17 16 9 8 7 6 19 20 13 12 2 1 5
    30:  5 4 3 10 11 15 16 9 8 7 17 18 14 13 12 2 1 20 19 6 5
    31:  5 4 8 7 6 19 18 17 16 9 10 3 2 12 11 15 14 13 20 1 5
    32:  5 4 8 7 6 19 20 13 12 11 15 14 18 17 16 9 10 3 2 1 5
    33:  5 4 8 7 17 16 9 10 3 2 1 20 13 12 11 15 14 18 19 6 5
    34:  5 4 8 7 17 18 14 13 12 11 15 16 9 10 3 2 1 20 19 6 5
    35:  5 4 8 9 10 3 2 1 20 19 18 14 13 12 11 15 16 17 7 6 5
    36:  5 4 8 9 10 3 2 12 11 15 16 17 7 6 19 18 14 13 20 1 5
    37:  5 4 8 9 16 15 11 10 3 2 12 13 14 18 17 7 6 19 20 1 5
    38:  5 4 8 9 16 15 14 13 12 11 10 3 2 1 20 19 18 17 7 6 5
    39:  5 4 8 9 16 15 14 18 17 7 6 19 20 13 12 11 10 3 2 1 5
    40:  5 4 8 9 16 17 7 6 19 18 14 15 11 10 3 2 12 13 20 1 5
    41:  5 6 7 8 4 3 2 12 13 14 15 11 10 9 16 17 18 19 20 1 5
    42:  5 6 7 8 4 3 10 9 16 17 18 19 20 13 14 15 11 12 2 1 5
    43:  5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5
    44:  5 6 7 8 9 16 17 18 19 20 1 2 12 13 14 15 11 10 3 4 5
    45:  5 6 7 17 16 9 8 4 3 10 11 15 14 18 19 20 13 12 2 1 5
    46:  5 6 7 17 16 15 11 10 9 8 4 3 2 12 13 14 18 19 20 1 5
    47:  5 6 7 17 16 15 11 12 13 14 18 19 20 1 2 3 10 9 8 4 5
    48:  5 6 7 17 16 15 14 18 19 20 13 12 11 10 9 8 4 3 2 1 5
    49:  5 6 7 17 18 19 20 1 2 3 10 11 12 13 14 15 16 9 8 4 5
    50:  5 6 7 17 18 19 20 13 14 15 16 9 8 4 3 10 11 12 2 1 5
    51:  5 6 19 18 14 13 20 1 2 12 11 15 16 17 7 8 9 10 3 4 5
    52:  5 6 19 18 14 15 11 10 9 16 17 7 8 4 3 2 12 13 20 1 5
    53:  5 6 19 18 14 15 11 12 13 20 1 2 3 10 9 16 17 7 8 4 5
    54:  5 6 19 18 14 15 16 17 7 8 9 10 11 12 13 20 1 2 3 4 5
    55:  5 6 19 18 17 7 8 4 3 2 12 11 10 9 16 15 14 13 20 1 5
    56:  5 6 19 18 17 7 8 9 16 15 14 13 20 1 2 12 11 10 3 4 5
    57:  5 6 19 20 1 2 3 10 9 16 15 11 12 13 14 18 17 7 8 4 5
    58:  5 6 19 20 1 2 12 13 14 18 17 7 8 9 16 15 11 10 3 4 5
    59:  5 6 19 20 13 12 11 10 9 16 15 14 18 17 7 8 4 3 2 1 5
    60:  5 6 19 20 13 14 18 17 7 8 4 3 10 9 16 15 11 12 2 1 5
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int a[21][3];
    int n;
    int vis[21]={0};
    int step[21]={0}; 
    int sum=0;
    void dfs(int s,int r){
     step[r]=s;
     if(r==19){
      for(int i=0;i<3;i++){
     if(a[s][i]==n){
      cout<<++sum<<":  ";
      for(int i=0;i<20;i++){
       cout<<step[i]<<" ";
      }
      cout<<n<<endl; 
      return ;
      
     }
      
     }} 
    for(int i=0;i<3;i++){
     if(vis[a[s][i]]==0){
     vis[a[s][i]]=1;
      dfs(a[s][i],r+1);
      vis[a[s][i]]=0; 
     }
      
    } 
     
    }
    int main(){
     //ios::sync_with_stdio(false);
     for(int i=1;i<=20;i++){
      scanf(" %d %d %d",&a[i][0],&a[i][1],&a[i][2]);
     }
     
     while(scanf("%d",&n)&&n){
      memset(vis,0,sizeof(vis));
      
      sum=0;
      vis[n]=1;
      dfs(n,0);
       vis[n]=0;
     }
     return 0;
    }

     

 

3条评论
  • AOne

    2017年3月31日 下午8:01

    dalao是杭电的不?

    1. zqqian

      2017年4月5日 下午11:00

      不是,只是在用杭电的平台练习

  • 随风

    2017年4月9日 上午1:20

    我都忘了是怎么知道这个网站的了

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注