【状压DP】回路计数【蓝桥杯】

题目

回路计数 - 蓝桥云课

---

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

蓝桥学院由 $21$ 栋教学楼组成，教学楼编号 $1$ 到 $21$。对于两栋教学楼 $a$ 和 $b$，当 $a$ 和 $b$ 互质时，$a$ 和 $b$ 之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。

小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？

两个访问方案不同是指存在某个 $i$，小蓝在两个访问方法中访问完教学楼 $i$ 后访问了不同的教学楼。

提示：建议使用计算机编程解决问题。

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

解题

方法一：动态规划

思路

本题类似于【状压DP】最短Hamilton路径，都是哈密顿圈问题。

在进行动态规划之前，先把教学楼 $1 \sim 21$ 映射为顶点 $0 \sim 20$，利用最大公约数是否等于 $1$ 来判断所有点两两之间是否互质，并填充邻接矩阵。

思维过程：

动态规划：

• 状态定义：$dp[i][j]$ 表示从顶点 $0$ 走到顶点 $j$，所有点的状态(即是否走过)为 $i$ (状态压缩)的所有路径。
• 状态转移方程：$dp[i][j] = dp[i][j] + dp[i-(1 <\!\!< j)][k]$ （$k \to j$ 为通路）。
• 初始状态：从顶点 $0$ 走到顶点 $0$ 只经过顶点 $0$ 的最短路径是：$dp[1_{(2)}][0] = 0$。

由于点教学楼 $1$ 与所有其它任何教学楼都互质，所以「从 $1$ 开始走一圈哈密顿回路回到 $1$ 的方案数」等于「从 $1$ 开始走一圈哈密顿回路到除 $1$ 以外的所有点的方案数之和」。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int n = 21, m = 1 << n;
    static boolean[][] g = new boolean[n][n];

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) throws IOException {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (gcd(i, j) == 1) g[i - 1][j - 1] = g[j - 1][i - 1] = true;
            }
        }
        long[][] dp = new long[m][n];
        dp[1][0] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i & (1 << j)) == 0) continue;
                int prev = i - (1 << j);
                for (int k = 0; k < n; ++k) {
                    if (g[j][k] && (prev & (1 << k)) != 0) {
                        dp[i][j] += dp[prev][k];
                    }
                }
            }
        }
        long cnt = 0;
        for (int i = 1; i < n; ++i) cnt += dp[m - 1][i];
        System.out.println(cnt);
    }
}