问题 F: [Usaco2009 Nov]lights 燈
时间限制: 1 Sec 内存限制: 64 MB
题目描述
贝希和她的闺密们在她们的牛棚中玩游戏。但是天不从人愿，突然，牛棚的电源跳闸了，所有的灯都被关闭了。贝希是一个很胆小的女生，在伸手不见拇指的无尽的黑暗中，她感到惊恐，痛苦与绝望。她希望您能够帮帮她，把所有的灯都给重新开起来！她才能继续快乐地跟她的闺密们继续玩游戏！牛棚中一共有N（1 <= N <= 35）盏灯，编号为1到N。这些灯被置于一个非常复杂的网络之中。有M（1 <= M <= 595）条很神奇的无向边，每条边连接两盏灯。每盏灯上面都带有一个开关。当按下某一盏灯的开关的时候，这盏灯本身，还有所有有边连向这盏灯的灯的状态都会被改变。状态改变指的是：当一盏灯是开着的时候，这盏灯被关掉；当一盏灯是关着的时候，这盏灯被打开。问最少要按下多少个开关，才能把所有的灯都给重新打开。数据保证至少有一种按开关的方案，使得所有的灯都被重新打开。
输入
＊第一行：两个空格隔开的整数：N和M。
＊第二到第M+1行：每一行有两个由空格隔开的整数，表示两盏灯被一条无向边连接在一起。没有一条边会出现两次。
输出
第一行：一个单独的整数，表示要把所有的灯都打开时，最少需要按下的开关的数目。
样例输入
5 6
1 2
1 3
4 2
3 4
2 5
5 3
輸入細節：
一共有五盞燈。燈1、燈4和燈5都連接著燈2和燈3。
样例输出
3
輸出細節：
按下在燈1、燈4和燈5上面的開關。
提示
是很像异或方程组（刚刚学会。。）
最终的状态（常数项）为1，代表亮了。如果两个灯连接，相应位置为一
而最后解出来对于每个灯，有的确定了状态，有的还是自由元（状态不确定），对于自由元，还要深搜确定最小解。
那么我们来从n到1倒叙枚举，
对于一个确定的，他的状态为他之后（已定的（也可以是dfs中暂定的自由元）的状态异或之和）再异或上常数项（开灭），就是自己的状态。
对于自由元，两种情况分别枚举，
对于这个方程，如果属于自己这一位系数是0，那自己是什么对自己的方程无影响，就可以枚举。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,ans=10000,sum,a[40][40],w[40];
inline void dfs(int x)
{
if(sum>=ans)return;
if(!x){if(sum<ans)ans=sum;return;}
if(a[x][x])
{
int l=a[x][n+1];
for(int i=x+1;i<=n;i++)if(a[x][i])l^=w[i];
w[x]=l;
if(l==1)sum++;
dfs(x-1);
if(l==1)sum--;
}
else
{
w[x]=0;dfs(x-1);
w[x]=1;sum++;dfs(x-1);sum--;
}
}
void gaosi()
{
int i,j,k;
for(int i=1;i<=n;i++)
{
j=i;
while(j<=n&&!a[j][i])j++;
if(j>n)continue;
if(i!=j)for(k=1;k<=n+1;k++)swap(a[i][k],a[j][k]);
for(j=1;j<=n;j++)
if(i!=j&&a[j][i]==1)
for(k=1;k<=n+1;k++)
a[j][k]^=a[i][k];
}
}
int main()
{
scanf("%d%d",&n,&m);int x,y;
for(int i=1;i<=n;i++)a[i][i]=1,a[i][n+1]=1;
for(int i=1;i<=m;i++)scanf("%d%d",&x,&y),a[x][y]=a[y][x]=1;
gaosi();
dfs(n);
cout<<ans;
}