洛谷题单指南-状态压缩动态规划-CF11D A Simple Task

原题链接：https://www.luogu.com.cn/problem/CF11D

题意解读：计算无向图中简单环的数量。

解题思路：

要计算环的数量，就需要计算每个点经过一系列点回到自己的路径条数。

为了避免重复计算，设定路径上经过的点中编号最小的是起点，要记录再次回到起点的路径条数！

可以这样来定义状态，设f[i][j]表示经过的点的状态为i，且最新到达的点为j的路径条数。

对于j相邻的所有点k，

如果k比i中最小的点还小，不合法的状态，不转移；

如果k在i中出现过，且就是i中最小的点，说明这条路径形成了环，要把答案累加f[i][j];

如果k在i中出现过，但不是最小的点，忽略掉；i中最小的点就是lowbit(i)的位置；

如果k在i中没有出现过，且是合法的点，则转移f[i | (1 << k)][k] += f[i][j]。

初始化根据定义来，对于所有点i，f[1<<i][i] = 1。

由于双向边的建立，此前环的统计算上了所有的二元环一次，其他环也都算了两次(顺时针、逆时针)，最终答案为(ans - m) / 2。
100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 20, M = 400;

int head[N], to[M], nxt[M], idx;
long long f[1 << N][N];
int n, m;
long long ans;

void add(int a, int b)
{
    to[++idx] = b;
    nxt[idx] = head[a];
    head[a] = idx;
}

int lowbit(int x)
{
    return x & -x;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--, v--; //为便于状态压缩后二进制位置表示点，编号从0开始更易处理
        add(u, v), add(v, u);
    }

    for(int i = 0; i < n; i++) f[1 << i][i] = 1;
    for(int i = 1; i < 1 << n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(!f[i][j]) continue; //不是一个有效的初始状态
            for(int x = head[j]; x; x = nxt[x])
            {
                int k = to[x];
                if(lowbit(i) > (1 << k)) continue; //k编号比i中最小的还小，不合法
                if(i >> k & 1) //k是i中的点
                {
                    if(lowbit(i) == (1 << k)) ans += f[i][j]; //k是i中的最小点，是环
                }
                else f[i | (1 << k)][k] += f[i][j];
            }
        }
    }

    cout << (ans - m) / 2; //由于双向边的建立，此前环的统计算上了所有的二元环，其他环也都算了两次
    return 0;
}