这道题比较简单,简述一下思路。
考虑状压 \(DP\)。
设 \(dp_{i,j}\) 表示走到第 \(i\) 个点,之前走过的点的状态为 \(j\) 的环的数量。这里有一个细节,就是我们都钦定每个走过的第一点是整个状态中编号最小的点,这样不会重复计算。
考虑如何进行转移。如果当前点的编号比走过的最小编号还小就直接跳过这种情况。如果当前点没有走过,就走;如果走过且形成了环的话,就把答案加上。
for(int i = 0;i < (1 << n);i++)
for(int j = 0;j < n;j++)
{
for(int k = head[j]; ~ k;k = e[k].nxt)
{
int now = e[k].v;
if((1 << now) < (i & -i)) continue;
if((1 << now) & i)
{
if((i & -i) == 1 << now) ans += dp[i][j];
}
else dp[(1 << now) | i][now] += dp[i][j];
}
}
因为是无向边,所以每个环会被计算两次,还会计算二元环。最后将这些减掉就可以了。
标签:Task,Simple,题解,走过,计算,编号 From: https://www.cnblogs.com/Creeperl/p/17913373.html