bzoj2466,poj1222

都是简单的异或高斯消元
由于bzoj2466要求解得最小和，所以我们最后还要穷举自由元取最优解
 1 type node=record
 2        po,next:longint;
 3      end;
 4 
 5 var f:array[0..110] of longint;
 6     a:array[0..110,0..110] of longint;
 7     i,x,y,ans,n:longint;
 8 
 9 procedure swap(var a,b:longint);
10   var c:longint;
11   begin
12     c:=a;
13     a:=b;
14     b:=c;
15   end;
16 
17 procedure dfs(k,sum:longint);
18   var j,p:longint;
19   begin
20     if sum>=ans then exit;
21     if k=0 then
22     begin
23       if ans>sum then ans:=sum;
24       exit;
25     end;
26     if a[k,k]=1 then
27     begin
28       p:=a[k,n+1];
29       for j:=k+1 to n do
30         if a[k,j]=1 then p:=p xor f[j];   //回代
31       f[k]:=p;
32       dfs(k-1,sum+f[k]);
33     end
34     else begin
35       f[k]:=0;
36       dfs(k-1,sum);
37       f[k]:=1;
38       dfs(k-1,sum+1);
39       f[k]:=0;
40     end;
41   end;
42 
43 procedure work;
44   var i,j,k,p:longint;
45   begin
46     for i:=1 to n do
47     begin
48       p:=i;
49       for j:=i to n do
50         if a[j,i]<>0 then
51         begin
52           p:=j;
53           break;
54         end;
55 
56      if p<>i then
57        for j:=1 to n+1 do
58          swap(a[i,j],a[p,j]);
59      if a[i,i]=0 then continue;
60      for k:=i+1 to n do
61        if a[k,i]<>0 then
62        begin
63          for j:=i to n+1 do
64            a[k,j]:=a[k,j] xor a[i,j];
65        end;
66     end;
67     ans:=361;
68     dfs(n,0);
69   end;
70 
71 begin
72   readln(n);
73   while n<>0 do
74   begin
75     fillchar(a,sizeof(a),0);
76     fillchar(f,sizeof(f),0);
77     for i:=1 to n-1 do
78     begin
79       readln(x,y);
80       a[x,y]:=1;
81       a[y,x]:=1;
82     end;
83     for i:=1 to n do
84     begin
85       a[i,i]:=1;
86       a[i,n+1]:=1;
87     end;
88     work;
89     writeln(ans);
90     readln(n);
91   end;
92 end.
bzoj2466