介绍

我们希望在二进制下枚举所有的 mask，并且枚举每个mask的所有子集。

for (int mask = 0; mask < (1 << n); mask++) {  // i 枚举所有物体的选择情况
    for (int sub = mask; sub; sub = (sub - 1) & mask) {  // j 枚举了 i 的子集
        ...
    }
}

原理

每次 sub 都相当于移除了最后一个 $1$，然后再和 mask AND 一下。

复杂度

考虑 mask 中 $bit$ 的数量，如果有 $i$ 个 $1$，那么就有 $C_n^i$ 种。而 submask 中，每个 $1$ 可选可不选，所以有 $2^i$ 种。

总复杂度为（由二项式定理可得）：

$$\sum\limits_{i=0}^n C_n^i 2^i = (1+2)^n = 3^n$$

例题

例1 Atcoder ABC187F. Close Group

题意

给定一个 $n$ 个节点，$m$ 条边的无向图，我们可以删除任意数量的边，使得删除后，每个联通块都是完全联通的（两两之间一定有边）。

求，在这样操作后，图中最少有多少个联通块？

其中，$1 \leq n \leq 18, 0 \leq m \leq \frac{n(n-1)}{2}$。

题解

很明显的二进制枚举。

令 int dp[mask] 为这个 mask 对应的最少联通块数量。

先处理 bool ok[mask] 判断一个mask是否已经完全联通。

然后枚举子集就可以了。

• 如果 mask 和 submask 都知道，计算 mask - submask 只要使用 XOR 即可。

代码 
#include <bits/stdc++.h>
using namespace std;
const int maxm = 5e5+505;

int n, m;
int adj[20][20];
int dp[maxm];
bool ok[maxm];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u,v; cin >> u >> v;
        adj[u][v] = adj[v][u] = 1;
    }
    for (int mask = 1; mask < (1<<n); mask++) {
        ok[mask] = 1;
        vector<int> vec;
        for (int j = 0; j < n; j++) {
            if (mask & (1<<j)) vec.push_back(j+1);
        }
        for (int i : vec) {
            for (int j : vec) {
                if (i != j && !adj[i][j]) {
                    ok[mask] = 0;
                    break;
                }
            }
        }
    }

    for (int mask = 1; mask < (1<<n); mask++) {
        dp[mask] = 1e9;
    }
    dp[0] = 0;
    for (int mask = 1; mask < (1<<n); mask++) {
        for (int sub = mask; sub; sub = (sub - 1) & mask) {
            if (ok[sub]) {
                dp[mask] = min(dp[mask], 1 + dp[mask ^ sub]);
            }
        }
    }
    cout << dp[(1<<n)-1] << endl;
}