CF11D A Simple Task

题目名称

问题

CF11D A Simple Task
求简单图中的简单环数量。
数据规模：$n \le 19$。

我的第一反应是 [[Floyd]] 的最小环统计 P6175 无向图的最小环问题,也就是这一题。但是这种做法只能找到最小的环，没法统计本题要求的所有简单环。

于是我们需要考虑新的做法了，但是前者的思路是可以借鉴的，简单回忆一下思路，在处理 $k$ 点之前，$dis[i][j]$ 表示只经过小于 $k$ 的顶点时，从 $i \to j$ 的最短路，然后用 $dis[i][j] + w[i][k] + w[k][j]$ 构成一个环。

因为对于同一个 $i, j, k$，可能有很多条不同的简单路径，每条路径都可能与 $i, j, k$ 组成不同的简单环，此时若是只记录一个最短距离，就会丢失掉很多环。

所以这一题我们还需要记录经过了那些点作为状态，同样借用上一题 P1171 售货员的难题 的状态定义，记 $f[mask][u]$ 表示恰好经过 mask 中的所有顶点，最终停在顶点 $u$ 的简单路径数量。

初始化 $f[1 \ll s][s] = 1$。

但是这样在实际运行的时候会出现问题，比如一个环 $i \to j \to k \to i$，可能就会被统计三次，分别从不同的点出发。为了去重，我们可以让每个新进入的点单调递增，这样就能保证所有找到的环是不重复的。

所以完善状态的定义：令 $s$ 为 mask 中编号最小的点，那么 $f[mask][u]$ 就表示从顶点 $s$ 出发，恰好经过 mask 中所有顶点，最终停在顶点 $u$ 的简单路径数量。

然后这里我们可以引入两个内置函数来方便我们处理：

1. __builtin_ctz( mask )，用来返回最低位 1 的位置，用于让新增的点单调递增。
2. __builtin_popcount( mask )，用来返回 mask 中有多少个 1，方便转移。

接着我们还需要考虑如何判断成环，若路径至少包括三个顶点，且终点 $u$ 与起点 $s$ 相邻，那就可以闭合成环。

if( __builtin_popcount( mask ) >= 3 && mat[u][s] )，由于无向环中存在正向和反向两种遍历方式，最终答案除以 2。

若是不限制路径至少包含三个点的话，每条无向边都可能会形成一个伪二元环 u -> v -> u，它重复使用同一条无向边，但不是合法的简单环。

因此另一种写法是，最后减去这些特殊的伪环 ( ans - m ) / 2。

注：lowbit 和 __builtin_ctz 二者的区别，lowbit 是最后一个 1，以及它之后 0 这个二进制转化为十进制的数值，而 __builtin_ctz 表示的是最后一个 1 的位置。

本题相较于普通的集合 DP 来说，多了一层 “去重” 的状态设计。我们采用了固定最小点，来消除不同的起点；除以 2，消除正反方向；最后排除两个点构成的伪环。

摘要

这类计数型状压，除了状态设计外，还必须明确每个对象是否会被枚举多次。