【题意】
同poj1830，但是求的是最小开关次数，保证有解
【题解】
高斯消元，再对自由元暴力枚举。暴力的时候要记得剪枝。
高斯消元优化很悬。。。其实有n个自由元的时候就相当于纯暴力了。似乎还有种可靠的折半写法。。。。
反正就当练习高斯消元了。
【代码】
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 struct node 6 { 7 int c,vec[40]; 8 }a[40]; 9 int n,m,ans,X[40],dt[40],kw[40],po,cnt,x,y; 10 void dfs(int t,int s) 11 { 12 if (s>=ans) return; 13 if (t>cnt) 14 { 15 for (int i=po;i;--i) 16 { 17 int y=a[i].c; 18 for (int j=kw[i]+1;j<=n;++j) 19 if (a[i].vec[j]) y^=X[j]; 20 X[kw[i]]=y; 21 s+=y; 22 } 23 if (s<ans) ans=s; 24 return; 25 } 26 X[dt[t]]=0; 27 dfs(t+1,s); 28 X[dt[t]]=1; 29 dfs(t+1,s+1); 30 } 31 void gauss() 32 { 33 for (int i=1,o=1;o<=n;) 34 { 35 for (int j=i;j<=n;++j) 36 if (a[j].vec[o]) 37 { 38 swap(a[i],a[j]); 39 break; 40 } 41 if (!a[i].vec[o]) 42 { 43 dt[++cnt]=o; 44 ++o; 45 continue; 46 } 47 for (int j=i+1;j<=n;++j) 48 if (a[j].vec[o]) 49 { 50 if (a[i].c) a[j].c^=1; 51 for (int k=o;k<=n;++k) 52 if (a[i].vec[k]) 53 a[j].vec[k]^=1; 54 } 55 kw[i]=o; 56 po=i;++i;++o; 57 } 58 } 59 int main() 60 { 61 scanf("%d%d",&n,&m); 62 for (int i=1;i<=n;++i) 63 a[i].vec[i]=1, 64 a[i].c=1; 65 for (int i=1;i<=m;++i) 66 { 67 scanf("%d%d",&x,&y); 68 a[x].vec[y]=1; 69 a[y].vec[x]=1; 70 } 71 gauss(); 72 ans=n; 73 dfs(1,0); 74 cout<<ans<<endl; 75 return 0; 76 }