HDU-2181 哈密顿绕行世界问题（dfs）

野性酷女 2022-02-13 08:57 181阅读 0赞

**Problem Description:**

一个规则的实心十二面体，它的 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

**思路：**

从起点开始dfs，在dfs的同时统计经过的节点的个数和存储依次经过的节点。统计进过的节点的个数用于最后判断是否一次dfs就遍历了所有的点，只有满足遍历了所有的点时才可以进行判断是否构成了哈密顿回路（由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次），若构成了哈密顿回路则直接将结果输出。

**判断哈密顿回路：只需要找到最后一个经过的节点，判断一下该节点和起点是不是直接相连。**

**上AC代码：**

#include <stdio.h>
    #include <string.h>
    bool Map[21][21];
    bool vis[21];
    //如果构成了哈密顿回路则用来存储哈密顿回路依次经过的节点
    int pos[21];
    //起点
    int m;
    //用于统计dfs经过的节点的个数
    int cntvis;
    //用于记录解的个数
    int t;
    //判断有没有构成哈密顿回路
    bool check(int st)
    {
        //判断dfs到的最后一个点有没有与起点相连
        //因为只有相连才能构成回路
        if(Map[pos[cntvis]][st]==false)
            return false;
        return true;
    }
    void dfs(int st)
    {
        int i,j;
        //此时已经遍历了图的所有节点
        if(cntvis>=20)
        {
            //检查一下有没有构成哈密顿回路
            if(check(m))
            {
                //若构成了哈密顿回路则直接输出结果
                t++;
                printf("%d:  %d",t,m);
                for(j=2;j<=cntvis;j++)
                {
                    printf(" %d",pos[j]);
                }
                printf(" %d\n",m);
            }
        }
        for(i=1;i<=20;i++)
        {
            if(Map[st][i]==true&&vis[i]==false)
            {
                //经过的节点数+1并存储经过的节点
                pos[++cntvis]=i;
                vis[i]=true;
                dfs(i);
                vis[i]=false;
                cntvis--;
            }
        }
    }
    int main()
    {
        int i;
        int a,b,c;
        memset(Map,0,sizeof(Map));
        for(i=1;i<=20;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            Map[i][a]=true;
            Map[a][i]=true;
            Map[i][b]=true;
            Map[b][i]=true;
            Map[i][c]=true;
            Map[c][i]=true;
        }
        while(~scanf("%d",&m))
        {
            if(m==0)
                break;
            //将解的个数初始化为0
            t=0;
            memset(vis,0,sizeof(vis));
            vis[m]=true;
            //先将起点存储进去
            pos[1]=m;
            cntvis=1;
            dfs(m);
        }
        return 0;
    }