将权值用二进制表示，由于到达n就立即停止，我们定义f[i]表示从i到达n的期望值。
那么显然f[n]=0,对于其他情况,我们列出其转移方程:
f[i]+=f[x]/deg[i] 若两边连边当前位为0
f[i]+=(1-f[x])/deg[i] 若两边连边当前位为1
然后就有n-1个方程，高斯消元求解，由于必有唯一解，写起来就方便多了。
最终的答案就是f[1]*2^当前位累加和
1 #include<cstdio> 2 #include<cstdlib> 3 #include<vector> 4 #include<algorithm> 5 #include<cmath> 6 #include<iostream> 7 #include<cstring> 8 using namespace std; 9 const int N=1010; 10 vector<pair<int,int> > G[N]; 11 int n,m,deg[N]; 12 double a[N][N]; 13 double ans[N]; 14 void Gauss(){ 15 m=n; 16 for(int col=0,k=0;k<m&&col<n;++k,++col){ 17 double Max=0; 18 int row=-1; 19 for(int r=k;r<m;++r) 20 if(Max<fabs(a[r][col])) 21 Max=fabs(a[r][col]),row=r; 22 23 swap(a[k],a[row]); 24 25 for(int r=k+1;r<m;++r){ 26 double tmp=-a[r][col]/a[k][col]; 27 for(int c=0;c<=n;++c) 28 a[r][c]+=a[k][c]*tmp; 29 } 30 } 31 for(int i=n-1;i>=0;--i){ 32 double tmp=a[i][n]; 33 for(int j=n-1;j>i;--j) 34 tmp-=a[i][j]*ans[j]; 35 ans[i]=tmp/a[i][i];//attention 36 } 37 } 38 int main(){ 39 scanf("%d%d",&n,&m); 40 while(m--){ 41 int u,v,w; 42 scanf("%d%d%d",&u,&v,&w); 43 --u,--v; 44 G[u].push_back(make_pair(v,w)); 45 ++deg[u]; 46 if(u!=v){ 47 ++deg[v]; 48 G[v].push_back(make_pair(u,w)); 49 } 50 } 51 double Ans=0.0; 52 for(int i=0;i<=30;++i){ 53 memset(a,0,sizeof(a)); 54 for(int x=0;x<n-1;++x){ 55 a[x][x]=1.0; 56 for(int j=0,j_end=G[x].size();j<j_end;++j){ 57 int v=G[x][j].first,w=G[x][j].second; 58 if(w&(1<<i))a[x][v]+=1.0/deg[x],a[x][n]+=1.0/deg[x]; 59 else a[x][v]-=1.0/deg[x]; 60 } 61 } 62 a[n-1][n-1]=1.0,Gauss(); 63 Ans+=(1<<i)*ans[0]; 64 } 65 printf("%.3lf ",Ans); 66 return 0; 67 }