题目大意：
每条路径上有一个距离值，从1走到N可以得到一个所有经过路径的异或和，求这个异或和的数学期望
这道题直接去求数学期望的DP会导致很难列出多元方程组
我们可以考虑每一个二进制位从1走到N的平均概率值
因为整个图是联通的那么所有点都默认会处于多元方程组中
Pi = p[i] * sigma( v&d[i][j]?(1-Pj):Pj)
v是当前二进制位代表的数值
这里需要注意的是自环的加边情况，自环只加一次边，不能向平时那样加无向边一样
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int N = ;
const int M = ;
#define eps 1e-8
int first[N] , k , degree[N] , n , m;
double p[N] , a[N][N]; void debug()
{
for(int i= ; i<n ; i++){
for(int j= ; j<=n ; j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
} struct Edge{
int y , next , d;
Edge(int y= , int next= , int d=):y(y),next(next),d(d){}
}e[M<<]; void add_edge(int x,int y,int d)
{
e[k] = Edge(y , first[x] , d);
first[x] = k++;
} int get_width(int x)
{
int ret = ;
while(x)
{
x>>=;
ret++;
}
return ret;
} void build(int v)
{
memset(a , , sizeof(a));
for(int i= ; i<n ; i++){
a[i][i] = ;
if(i==n-) continue;
for(int j=first[i] ; ~j ; j=e[j].next){
int u = e[j].y;
if(v&e[j].d){
a[i][u] += p[i];
a[i][n] += p[i];
}else{
a[i][u] -= p[i];
}
}
}
// debug();
} int gauss(int n)
{
int i,j,k;
for(i= , j= ; i<n&&j<n ; j++){
for(k=i ; k<n ; k++)
if(fabs(a[k][j])>eps) break;
if(k<n){
if(i!=k)
for(int r=j ; r<=n ; r++) swap(a[i][r],a[k][r]);
double tt = 1.0/a[i][j];
for(int r=j ; r<=n ; r++) a[i][r] *= tt;
for(int r= ; r<n ; r++){
if(r == i) continue;
for(int t=n ; t>=j ; t--)
a[r][t] -= a[i][t]*a[r][j];
}
i++;
}
}
for(int r=i ; r<n ; r++)
if(fabs(a[r][n])>eps) return ;
return ;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in" , "r" , stdin);
#endif // ONLINE_JUDGE
while(~scanf("%d%d" , &n , &m))
{
memset(first , - , sizeof(first));
memset(degree , , sizeof(degree));
k = ;
int maxn = ;
for(int i= ; i<m ; i++){
int x,y,d;
scanf("%d%d%d" , &x , &y , &d);
add_edge(x-,y-,d);
if(x!=y){
add_edge(y- , x- , d);
degree[x-]++ , degree[y-]++;
}
else degree[x-]++;
maxn = max(maxn , d);
}
for(int i= ; i<n ; i++) p[i] = 1.0/(degree[i]*1.0);//得到从当前点每条边出发的概率
int len = get_width(maxn);
double ret= ;
for(int i= ; i<len ; i++){
int v = <<i;
build(v);
gauss(n);
ret += v*a[][n];
}
printf("%.3f\n" , ret);
}
return ;
}