解题思路
把每种原材料看成一个点,冲突看成一条边。
一份披萨就是选择一些原材料的集合,要求集合里任意两种原材料不冲突,也就是图中的一个独立集。
题目问“最多能做多少种不同披萨”,等价于:
* 统计这个图一共有多少个独立集(包含空集)
因为 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++ 代码(普通数组版)