地址：https://www.luogu.com.cn/problem/P2962
算法分类：双向搜索、枚举、状压
题目原文：
Lights G
Problem Description
Bessie and the cows were playing games in the barn, but the power was reset and the lights were all turned off. Help the cows get all the lights back on so they can resume their games.
The N (1 <= N <= 35) lights conveniently numbered 1..N and their switches are arranged in a complex network with M (1 <= M <= 595) clever connection between pairs of lights (see below).
Each light has a switch that, when toggled, causes that light -- and all of the lights that are connected to it -- to change their states (from on to off, or off to on).
Find the minimum number of switches that need to be toggled in order to turn all the lights back on.
It's guaranteed that there is at least one way to toggle the switches so all lights are back on.
Input
Line 1: Two space-separated integers: N and M. Lines 2..M+1: Each line contains two space-separated integers representing two lights that are connected. No pair will be repeated.
Output
Line 1: A single integer representing the minimum number of switches that need to be flipped in order to turn on all the lights.
Sample Input
5 6 1 2 1 3 4 2 3 4 2 5 5 3
Sample Output
3
Explanation
There are 5 lights. Lights 1, 4, and 5 are each connected to both lights 2 and 3.
Toggle the switches on lights 1, 4, and 5.
题目大意：
给出一张 n 个点 m 条边的无向图，每个点的初始状态都为 0。
你可以操作任意一个点，操作结束后所有相邻的端点的状态都会改变，由 0 变成 1 或由 1 变成 0。
你需要求出最少的操作次数，使得在所有操作完成之后所有 n 个点的状态都是 1。
输入第一行为两个整数n，m。之后的m行，每行两个整数a，b，表示a与b之间有一条边。
要求输出一行整数，表示最少操作次数。
题目分析
关于开灯与关灯状态的题，可以使用状态压缩思想，进行枚举，结合异或运算。
由于灯数较多，如果暴力搜索进行枚举的话，那么时间复杂度就达到了O(), 显然超时。因此，在此我们可以使用双向搜索（折半搜索）就能将时间复杂度降为O()
先枚举前一半的编号为1 - n/2 的灯的操作方案以及达到的状态，再枚举编号后一半的灯，如果某个操作能达到的状态与前一半的灯状态互补，那么，这前一段与后一段的操作方案合起来就是问题的解决方案。
具体实现状态与方案数的映射关系可以用map，状态与方案都可以用整数的二进制位表示。
程序代码
1 #include<iostream> 2 #include<string.h> 3 #include<map> 4 /*双向搜索 meet in middle*/ 5 /*先搜前一半灯的状态 再通过搜后一半的状态 如与前一半互补 则保存答案 取最小值*/ 6 using namespace std; 7 typedef long long ll; 8 int n, m, ans = 1<<30; 9 map <ll, int> f;//由 灯的状态 - 操作数 10 ll a[40]; 11 int u, v; 12 int main() 13 { 14 cin>>n>>m; 15 for(int i=0;i<n;i++)a[i] = (1ll<<i);//预处理 16 for(int i=0;i<m;i++) 17 { 18 cin>>u>>v; 19 u--; 20 v--; 21 a[u]|=(1ll<<v); 22 a[v]|=(1ll<<u); 23 }//预处理 可表示灯的链接状态 也可用于后续表示灯的状态是否被改变 24 for(int i=0;i<(1<<(n/2));i++)//枚举前一半灯的操作方案 25 { 26 int cnt=0; 27 ll t=0; 28 for(int j=0;j<n/2;j++) 29 { 30 if((i>>j)&1) 31 { 32 t^=a[j]; 33 cnt++; 34 } 35 }//最终得到按 i 的开灯方案 有哪些灯的状态被改变 及 操作次数cnt 36 if(!f.count(t)) 37 f[t]=cnt; 38 else 39 f[t]=min(f[t], cnt); 40 } 41 for(int i=0;i<(1<<(n-n/2));i++)//枚举后一半灯的操作方案 42 { 43 int cnt=0; 44 ll t=0; 45 for(int j=0;j<(n-n/2);j++) 46 { 47 if((i>>j)&1) 48 { 49 t^=a[n/2+j]; 50 cnt++; 51 } 52 } 53 if(f.count(((1ll<<n)-1)^t))//如果操作后一半灯后能改变的状态刚好能与前一半互补 54 ans=min(ans, cnt+f[((1ll<<n)-1)^t]); 55 } 56 cout<<ans; 57 //system("pause"); 58 return 0; 59 }
程序分析
map大法好，用二进制表示灯的状态或操作方案，异或运算需要用得行云流水。在枚举方案时，二进制位中的1表示进行开关操作，在改变灯的状态时，对于每一盏灯，二进制位中的1表示与其相连的灯，要改变灯的状态，只需对其进行异或运算即可。最终只需使每盏灯的状态都被改变（一次）即可。搜索后一半与搜索前一半方法类似，合理修改代码可使代码简洁清晰，编写流畅。
心得
灯数有点多，不能用int，得用long long才行。对于这种0/1状态的题感觉都与二进制，枚举，位运算等有关，希望以后碰到类似的题能够快速反应，举一反三。如果发现题目单纯搜索会超时，可以尝试一下双向搜，感觉也复杂不了多少。另外，还看到有用高斯消元做的这个题目的，但是我还没有学习这个方法，先插个flag，后期做。还有，灯数组变成灯图，感觉难了不少，写的时候都没有思路了。还要加强对图类题目的练习啊。