T13:GEPPETTO

解题思路

把每种原材料看成一个点，冲突看成一条边。

一份披萨就是选择一些原材料的集合，要求集合里任意两种原材料不冲突，也就是图中的一个独立集。

题目问“最多能做多少种不同披萨”，等价于：

• 统计这个图一共有多少个独立集（包含空集）

因为 N ≤ 20，可以直接用二进制枚举所有子集，判断是否为独立集即可。

做法

1. 用 ban[i] 记录与 i 冲突的点集合（一个 bitmask）。

2. 枚举所有子集 mask（0 到 2^N - 1）。

3. 判断 mask 是否为独立集：

   可以用“逐个取出 mask 中的点”来检查是否出现冲突：

   • 取出一个点 v
   • 如果 mask 里还包含 ban[v] 里的点，则冲突，失败

4. 统计通过的子集数量。

复杂度大约是 O(N * 2^N)，N=20 时大约两千多万次操作，1 秒一般能过。

---

C++ 代码（普通数组版）

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

unsigned int banMask[25];  // banMask[i]：与 i 冲突的点的集合（bitmask）

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    // 初始化
    for (int i = 0; i < N; i++) banMask[i] = 0;

    // 读入冲突边（无向）
    for (int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        --x; --y; // 转成 0..N-1
        banMask[x] |= (1u << y);
        banMask[y] |= (1u << x);
    }

    long long ans = 0;
    int FULL = 1 << N;

    // 枚举所有子集
    for (int mask = 0; mask < FULL; mask++) {
        bool ok = true;
        int s = mask;

        // 检查是否为独立集
        while (s) {
            int lb = s & -s;                  // 取最低位的 1
            int v = __builtin_ctz(lb);        // v = 这个 1 的下标
            s ^= lb;                          // 去掉 v

            // 如果剩余集合里包含 v 的冲突点，则不是独立集
            if (s & (int)banMask[v]) {
                ok = false;
                break;
            }
        }

        if (ok) ans++;
    }

    cout << ans << endl;
    return 0;
}