2337:[HNOI2011]XOR和路径 - BZOJ

 1 var
 2     f:array[0..110,0..110]of extended;
 3     d:array[0..110]of longint;
 4     v,u,w:array[0..10010]of longint;
 5     ans:extended;
 6     n,m:longint;
 7  
 8 procedure swap(var x,y:extended);
 9 var
10     t:extended;
11 begin
12     t:=x;
13     x:=y;
14     y:=t;
15 end;
16  
17 procedure init;
18 var
19     i:longint;
20 begin
21     read(n,m);
22     for i:=1 to m do
23       begin
24         read(v[i],u[i],w[i]);
25         inc(d[v[i]]);
26         inc(d[u[i]]);
27         if u[i]=v[i] then dec(d[u[i]]);
28       end;
29 end;
30  
31 procedure work;
32 var
33     t,i,j,k:longint;
34     s:extended;
35 begin
36     for t:=0 to 30 do
37       begin
38         for i:=1 to n do
39           for j:=1 to n+1 do
40             f[i,j]:=0;
41         for i:=1 to n do
42           f[i,i]:=1;
43         for i:=1 to m do
44           if w[i]and(1<<t)=0 then
45             begin
46               f[v[i],u[i]]:=f[v[i],u[i]]-1/d[v[i]];
47               f[u[i],v[i]]:=f[u[i],v[i]]-1/d[u[i]];
48               if u[i]=v[i] then f[v[i],v[i]]:=f[u[i],u[i]]+1/d[v[i]];
49             end
50           else
51             begin
52               f[v[i],u[i]]:=f[v[i],u[i]]+1/d[v[i]];
53               f[u[i],v[i]]:=f[u[i],v[i]]+1/d[u[i]];
54               f[v[i],n+1]:=f[v[i],n+1]+1/d[v[i]];
55               f[u[i],n+1]:=f[u[i],n+1]+1/d[u[i]];
56               if v[i]=u[i] then
57               begin
58                 f[u[i],v[i]]:=f[u[i],v[i]]-1/d[u[i]];
59                 f[v[i],n+1]:=f[v[i],n+1]-1/d[v[i]];
60               end;
61             end;
62         for i:=1 to n-2 do
63           begin
64             for j:=i to n-1 do
65               if f[j,i]<>0 then break;
66             for k:=i to n+1 do
67               swap(f[i,k],f[j,k]);
68             for j:=i+1 to n-1 do
69               if abs(f[j,i])>0 then
70               begin
71                 s:=f[j,i]/f[i,i];
72                 f[j,i]:=0;
73                 for k:=i+1 to n+1 do
74                   f[j,k]:=f[j,k]-s*f[i,k];
75               end;
76           end;
77           for i:=n-1 downto 1 do
78             begin
79               for j:=i+1 to n-1 do
80                 f[i,n+1]:=f[i,n+1]-f[j,0]*f[i,j];
81               f[i,0]:=f[i,n+1]/f[i,i];
82             end;
83           ans:=ans+f[1,0]*(1<<t);
84       end;
85     write(ans:0:3);
86 end;