动态规划之【状压DP】第4课：状压DP应用案例实践3
GEPPETTO
题目描述
Geppetto 开了一家披萨店，他正在努力做出全市最好的披萨。
Geppetto 用N NN种原材料做比萨，每种原材料只有一个。原材料标号为1 11到N NN。做披萨很简单，只要把原材料混合好然后放进烤箱里烤一烤就行了。但 Geppetto 发现一共有M MM对原材料是冲突的，如果一对冲突的原材料混合在一份披萨里，这份披萨就会变得十分难吃。这给他带来了额外的麻烦。
Geppetto 想知道他最多能做多少种不同的比萨。如果一份比萨上有编号为i ii的原材料，而另一份比萨上没有，那么这两份比萨就是不同的。
输入格式
第一行两个整数N , M N,MN,M，分别表示原材料总数和冲突总数。
接下来M MM行，每行两个整数x i , y i x_i,y_ixi,yi，表示一对冲突中两种原材料的编号。
输出格式
一行一个整数，表示 Geppetto 最多能做多少种披萨。
输入输出样例 1
输入 1
3 2 1 2 2 3输出 1
5输入输出样例 2
输入 2
3 0输出 2
8输入输出样例 3
输入 3
3 3 1 2 1 3 2 3输出 3
4说明/提示
【样例 1 解释】
Geppetto 可以做出以下4种披萨：
1
2
3
1 3
不过因为 Geppetto 可以不放原材料，所以最多可以做出5种披萨。
【样例 2 解释】
没有原材料冲突，所以一共可以做出2 3 = 8 2^3=823=8种披萨。
【样例 3 解释】
由于所有原材料都互相冲突，所以 Geppetto 只能放一种原材料或者不放原材料，一共可以做出1 + 3 = 4 1+3=41+3=4种披萨。
【数据范围】
对于100 % 100\%100%的数据，1 ≤ N ≤ 20 ， 0 ≤ M ≤ 400 ， 1 ≤ x i , y i ≤ N 1\le N\le 20，0\le M\le 400，1\le x_i,y_i\le N1≤N≤20，0≤M≤400，1≤xi,yi≤N，保证x i ≠ y i x_i\ne y_ixi=yi。
题目分析
题目要求计算使用N NN种原材料制作披萨的方案数，其中原材料编号1 ∼ N 1 \sim N1∼N，每种原料最多用一次（即选取一个子集）。有M MM对冲突关系，如果一个披萨中同时包含某一对冲突的原材料，则该披萨不可行。需要统计所有可行的披萨种类（包括空披萨，即什么都不放）。
N ≤ 20 N \le 20N≤20，因此总子集数为2 N 2^N2N，直接枚举所有子集并检查冲突是可行的。
思路分析
- 将原材料编号映射为0 ∼ N − 1 0 \sim N-10∼N−1，方便位运算处理。
- 用一个整数s ss的二进制位表示子集：第i ii位为1 11表示选取了原材料i ii。
- 枚举s ss从0 00到2 N − 1 2^N - 12N−1。
- 对于每个子集s ss，检查所有M MM对冲突( x , y ) (x, y)(x,y)：如果s ss中同时包含x xx和y yy（即
(s>>x & 1) && (s>>y & 1)为真），则该子集非法，否则合法。 - 统计合法子集个数，即为答案。
时间复杂度O ( 2 N ⋅ M ) O(2^N \cdot M)O(2N⋅M)，最坏约4 × 10 8 4 \times 10^84×108次操作，C++ 在极限数据下可能略慢，但通常可接受。
代码实现
#include<bits/stdc++.h>// 万能头文件usingnamespacestd;intn,m,a[410],b[410];// a,b 存储冲突对的两端，数组大小根据 M≤400 开够intmain(){// 输入原材料数 n 和冲突对数 mcin>>n>>m;for(inti=0;i<m;++i){cin>>a[i]>>b[i];// 将编号转换为 0~n-1，方便位运算--a[i];--b[i];}intans=0;// 答案计数// 枚举所有子集，s 从 0 到 (1<<n)-1for(ints=0;s<(1<<n);++s){boolok=true;// 标记当前子集是否合法// 检查所有冲突对for(inti=0;i<m;++i){// 如果子集中同时包含 a[i] 和 b[i] 这两个原料if((s>>a[i]&1)&&(s>>b[i]&1)){ok=false;// 非法，退出检查break;}}if(ok)++ans;// 合法则计数}cout<<ans<<endl;return0;}功能分析
- 算法原理：暴力枚举 + 冲突检测。利用二进制位表示子集，通过位运算快速判断某个元素是否在子集中。
- 时间复杂度：O ( 2 N ⋅ M ) O(2^N \cdot M)O(2N⋅M)，当N = 20 , M = 400 N=20, M=400N=20,M=400时，约为4 × 10 8 4 \times 10^84×108次检查，实际运行在评测环境下可接受。
- 空间复杂度：O ( M ) O(M)O(M)，仅存储冲突对。
- 适用性：N NN较小（≤20）时非常有效；若N NN更大则需考虑其他方法（如 DP、容斥等）。
- 边界情况：
- M = 0 M=0M=0：无冲突，答案为2 N 2^N2N。
- 冲突对可能重复？题目未说明，但即使重复也不影响结果（重复检查不影响正确性，可优化去重但没必要）。
- 空集（s = 0 s=0s=0）总是合法。
完整系列资料，请查看专栏：《csp信奥赛C++动态规划》
https://blog.csdn.net/weixin_66461496/category_13096895.html
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}【秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
https://edu.csdn.net/course/detail/41081 点击跳转
3、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转
4、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转
5、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;})
