【BZOJ 1770】[Usaco2009 Nov] lights 燈

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1770
离线版题目：http://paste.ubuntu.com/18956597/
数据生成器：http://paste.ubuntu.com/18956646/

首先，这道题状态压缩的方法很显然，但是状态太多了，会T（然而黄学长说：折半搜索也可过QAQ）
然后开始想高斯消元。一开始不知道高斯消元能解异或方程组，于是想了两个多小时QAQ
然后去补了解异或方程组，一开始对自由元的理解有问题，正确的应该是：
自由元可以随便定，每一组不同的自由元可以导出一组方程的解
换一句话说，消完元之后，非自由元的未知数的解，并非最终解

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 50;
const int INF = 50;

int n,m,vout=INF;
int mat[MAXN][MAXN],tag[MAXN];

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

inline void Gauss(){
	for (int k=1,w=k;k<n;w=++k){
		for (int i=k+1;i<=n&&!mat[k][w];i++) if (mat[k][i]) w = i;
		for (int i=1;i<=n+1;i++) swap(mat[i][w],mat[i][k]);
		for (int i=k+1;i<=n;i++) if (mat[k][i]) 
			for (int j=1;j<=n+1;j++) mat[j][i] ^= mat[j][k];
	}
}

void DFS(int w, int cost){
	if (cost >= vout) return;
	else if (!w) vout = min(vout, cost);
	else {
		if (mat[w][w]) {
			int t = mat[n+1][w];
			for (int i=w+1;i<=n;i++)
				if (mat[i][w]) t ^= tag[i];
			tag[w] = t;
			DFS(w-1, cost+(t?1:0));
		} else {
			tag[w] = 1;
			DFS(w-1, cost+1);
			tag[w] = 0;
			DFS(w-1, cost);
		}
	}
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=n;i++) 
		mat[i][i] = 1, mat[n+1][i] = 1;
	for (int i=1,a,b;i<=m;i++){
		a = read(); b = read();
		mat[a][b] = mat[b][a] = 1;
	}
	Gauss(); 
	DFS(n,0);
	printf("%d\n",vout);
	return 0;
}