又是一关于操作灯开关的题目。
一眼看去就知道是高斯消元。
但是，该题的重点是输出一个最小操作数的解！
这就需要进行枚举自由变元了！
如果学习过线性代数的话就知道了。
将矩阵转为下三角矩阵后。
有一种东西叫关键元。就是每一行的第一个非零元。
通常来讲这个第i行的关键元应该在第i列才对。
否则就会出现多解的问题。
那么如果多解的话。这个本来应该是关键元的地方就成了自由变元了。
就需要枚举这个位置的值，还好只有1,0两种。
直接从最下面一行DFS深搜，然后剪枝即可。
参考了 一个文章
http://blog.sina.com.cn/s/blog_51cea4040100g7hl.html
代码也是扒的
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#define MAXN 200115
#define MAXM 500005
#define INF 1000000000
using namespace std;
int mp[55][55];
int m[55][55];
int b[55];
int x[55];
int n, M;
void build()
{for(int i = 1; i <= n; i++) b[i] = 1;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)m[i][j] = mp[i][j];
}
void Swap(int i, int j)
{for(int k = 1; k <= n; k++) swap(m[i][k], m[j][k]);swap(b[i], b[j]);
}
void Xor(int i, int j)
{for(int k = 1; k <= n; k++) m[i][k] ^= m[j][k];b[i] ^= b[j];
}
int ans, v[55];
void dfs(int k, int num)
{if(num >= ans) return;if(k == 0){if(num < ans) ans = num;return;}if(m[k][k]){int now = b[k];for(int i = k + 1; i <= n; i++)if(m[k][i]) now ^= v[i];v[k] = now;if(v[k]) dfs(k - 1, num + 1);else dfs(k - 1, num);}else{v[k] = 0; dfs(k - 1, num);v[k] = 1; dfs(k - 1, num + 1);v[k] = 0;}
}
void work()
{for(int k = 1; k <= n; k++){bool flag = false;for(int i = k; i <= n; i++)if(m[i][k]){flag = true;Swap(i, k);break;}if(flag == false) continue;for(int i = k + 1; i <= n; i++)if(m[i][k]) Xor(i, k);}ans = INF;dfs(n, 0);printf("%d\n", ans);
}
int main()
{int u, v;scanf("%d%d", &n, &M);for(int i = 1; i <= n; i++) mp[i][i] = 1;for(int i = 1; i <= M; i++){scanf("%d%d", &u, &v);mp[u][v] = mp[v][u] = 1;}build();work();return 0;
}