侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-12-27 / 0 评论 / 0 点赞 / 14 阅读 / 788 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-28,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

回路计数 - 蓝桥云课


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

蓝桥学院由 2121 栋教学楼组成,教学楼编号 112121。对于两栋教学楼 aabb,当 aabb 互质时,aabb 之间有一条走廊直接相连,两个方向皆可通行,否则没有直接连接的走廊。

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

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

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

运行限制

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

解题

方法一:动态规划

思路

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

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

思维过程:

image-20221227185543111

动态规划:

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

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

代码

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);
    }
}
0

评论区