高斯消元解XOR方程组
一眼看上去是高斯消元解xor方程组……但是不会写……sad
Hzwer啥也没说，还是zyf靠谱……
当多解的时候就需要爆搜枚举*元的情况，找最优解……
o(︶︿︶)o 唉我还是太弱了
zyf的解释：
inline void dfs(int x)
{
if(tot>=mn)return;//最优性剪枝
if(!x){mn=min(mn,tot);return;}//终点
if(f[x][x])//已被限制是否需要按下
{
int t=f[x][n+];
for2(i,x+,n)if(f[x][i])t^=ans[i];
ans[x]=t;
if(t)tot++;
dfs(x-);//继续深搜
if(t)tot--;//还原，回溯
}
else//*变量
{
ans[x]=;dfs(x-);//假设不按该灯开关
ans[x]=;tot++;dfs(x-);tot--;//假设按该灯开关
}
}
/**************************************************************
Problem: 1770
User: Tunix
Language: C++
Result: Accepted
Time:4 ms
Memory:1284 kb
****************************************************************/ //BZOJ 1770
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
const int N=;
typedef long long LL;
int n,m,f[N][N],_min=1e7,ans[N],tot; void gauss(){
F(i,,n){
int j=i;
while(j<=n && !f[j][i]) j++;
if(j>n) continue;
if(i!=j) F(k,,n+) swap(f[i][k],f[j][k]);
F(j,,n) if(i!=j && f[j][i])
F(k,,n+) f[j][k]^=f[i][k];
}
}
void dfs(int x){
if(tot>=_min) return;
if(!x){
_min=min(_min,tot);
return;
}
if(f[x][x]){
int t=f[x][n+];
F(i,x+,n)
if(f[x][i]) t^=ans[i];
ans[x]=t;
if(t) tot++;
dfs(x-);
if(t) tot--;
}
else{
ans[x]=; dfs(x-);
ans[x]=; tot++; dfs(x-); tot--;
}
}
int main(){
scanf("%d%d",&n,&m);
F(i,,n) f[i][i]=f[i][n+]=;
int x,y;
F(i,,m){
scanf("%d%d",&x,&y);
f[x][y]=f[y][x]=;
}
gauss();
dfs(n);
printf("%d\n",_min);
return ;
}