【高斯消元解xor方程组】BZOJ2466-[中山市选2009]树

【题目大意】

给出一棵树，初始状态均为0，每反转一个节点的状态，相邻的节点（父亲或儿子）也会反转，问要使状态均为1，至少操作几次？

【思路】

一场大暴雨即将来临，白昼恍如黑夜！happy！

和POJ1222差不多，首先容易知道：每个节点最多被反转一次，证明略。

高斯消元解Xor方程组可能存在自由元，即处理完后map[i][i]=0;则通过dfs来枚举所有的情况，求出最小的。

【错误点】

gauss里面交换值得时候不要忘了n+1也要跟着交换。

dfs里面的t我一开始直接是按照往常一样修改map[i][n+1],然而这个是dfs，map[i][n+1]的初始值后面还要用到。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=100+5;
 7 const int INF=0x7fffffff;
 8 int n,map[MAXN][MAXN],que[MAXN];
 9 int ans;
10  
11 void Gauss()
12 {
13     for (int i=1;i<=n;i++)
14     {
15         int t=i;
16         for (;t<=n && !map[t][i];t++);
17         if (t<=n)
18         {
19             if (t!=i) for (int j=i;j<=n+1;j++) swap(map[i][j],map[t][j]);
20             for (int j=i+1;j<=n;j++)
21                 if (map[j][i])
22                     for (int k=i;k<=n+1;k++) map[j][k]^=map[i][k];//不要忘记这里要到n+1 
23         }
24     }
25 }
26  
27 void dfs(int step,int now)
28 {
29     if (now>=ans) return;
30     if (!step)
31     {
32         ans=min(ans,now);
33         return;
34     } 
35     if (map[step][step])
36     {
37         int t=map[step][n+1];
38         //map[step][n+1]后续回溯中还要使用，所以要暂存给t 
39         for (int i=step+1;i<=n;i++)
40             if (map[step][i]) t^=que[i];//这里不要把step和i搞混了 
41         que[step]=t;
42         dfs(step-1,now+t);
43     }
44     else
45     {
46         que[step]=0;dfs(step-1,now);
47         que[step]=1;dfs(step-1,now+1);
48     }
49 }
50  
51 void init()
52 {
53     ans=INF;
54     memset(que,0,sizeof(que));
55     memset(map,0,sizeof(map));
56     for (int i=0;i<n-1;i++)
57     {
58         int u,v;
59         scanf("%d%d",&u,&v);
60         map[u][v]=map[v][u]=1;
61     }
62     for (int i=1;i<=n;i++) map[i][i]=1,map[i][n+1]=1;
63 }
64  
65 int main()
66 {
67     while (~scanf("%d",&n))
68     {
69         if (n==0) break;
70         init();
71         Gauss();
72         dfs(n,0);
73         printf("%d
",ans);
74     }
75     return 0;
76 }