★★☆ 输入文件：lights.in 输出文件：lights.out 简单对比 时间限制：1 s 内存限制：128 MB
【问题描述】
贝希和她的闺密们在她们的牛棚中玩游戏。但是天不从人愿，突然，牛棚的电源跳闸了，所有的灯都被关闭了。贝希是一个很胆小的女生，在伸手不见拇指的无尽的黑暗中，她感到惊恐，痛苦与绝望。她希望您能够帮帮她，把所有的灯都给重新开起来！她才能继续快乐地跟她的闺密们继续玩游戏！
牛棚中一共有N（1 <= N <= 35）盏灯，编号为1到N。这些灯被置于一个非常复杂的网络之中。有M（1 <= M <= 595）条很神奇的无向边，每条边连接两盏灯。
每盏灯上面都带有一个开关。当按下某一盏灯的开关的时候，这盏灯本身，还有所有有边连向这盏灯的灯的状态都会被改变。状态改变指的是：当一盏灯是开着的时候，这盏灯被关掉；当一盏灯是关着的时候，这盏灯被打开。
问最少要按下多少个开关，才能把所有的灯都给重新打开。
数据保证至少有一种按开关的方案，使得所有的灯都被重新打开。
题目名称：lights
输入格式：
＊第一行：两个空格隔开的整数：N和M。
＊第二到第M+1行：每一行有两个由空格隔开的整数，表示两盏灯被一条无向边连接在一起。
没有一条边会出现两次。样例输入（文件 lights.in）：
5 6
1 21 34 23 42 55 3输入细节：
一共有五盏灯。灯1、灯4和灯5都连接着灯2和灯3。
输出格式：
第一行：一个单独的整数，表示要把所有的灯都打开时，最少需要按下的开关的数目。
样例输出（文件 lights.out）：
3
输出细节：
按下在灯1、灯4和灯5上面的开关。
题解：
和poj 1681几乎一样，dfs的不懂的。。。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 using namespace std;10 int N,M,ANS;11 int a[50][50];12 void gauss(){13 for(int i=1;i<=N;i++){14 int tmp=i;15 while(tmp<=N&&a[tmp][i]==0) tmp++;16 if(tmp>N) continue;17 if(tmp!=i){18 for(int j=1;j<=N+1;j++) swap(a[i][j],a[tmp][j]);19 }20 for(int j=1;j<=N;j++){21 if(j!=i&&a[j][i]==1){22 for(int k=1;k<=N+1;k++) a[j][k]^=a[i][k];23 }24 }25 }26 }27 int s[50],cnt;28 void dfs(int x){29 if(cnt>=ANS) return;30 if(x==0){31 ANS=min(ANS,cnt);32 return;33 }34 if(a[x][x]){35 int num=a[x][N+1];36 for(int i=x+1;i<=N;i++)37 if(a[x][i])38 num=num^s[i];39 s[x]=num;40 if(num==1) cnt++;41 dfs(x-1);42 if(num==1) cnt--;43 }44 if(!a[x][x]){45 s[x]=0;46 dfs(x-1); s[x]=1; cnt++;47 dfs(x-1); cnt--;48 }49 }50 int main(){51 //freopen("lights.in","r",stdin);52 //freopen("lights.out","w",stdout);53 scanf("%d%d",&N,&M);54 for(int i=1;i<=N;i++) a[i][i]=1;55 for(int i=1,u,v;i<=M;i++){56 scanf("%d%d",&u,&v);57 a[u][v]=a[v][u]=1;58 }59 for(int i=1;i<=N;i++) a[i][N+1]=1;60 gauss();61 ANS=1<<28;62 dfs(N);63 printf("%d",ANS);64 return 0;65 }